Results 1 to 8 of 8

Math Help - Strong Mathematical Induction

  1. #1
    Newbie
    Joined
    Mar 2010
    Posts
    20

    Strong Mathematical Induction

    So, I'm trying to prove that for each positive integer n, there exist positive integers x,y,z such that
    Strong Mathematical Induction-equation.gif
    I know I need to use strong mathematical induction. I've also got two base steps(ie. n=1,2).

    Can anyone push me in the right direction?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member
    Joined
    Jul 2010
    From
    Vancouver
    Posts
    432
    Thanks
    17
    In the normal mathematical induction you are assuming the statement P is true for some value, say k, that is P(k) is true. Then you try to manipulate P(k+1) to something that will use P(k). That is, when considering P(k+1), you are falling back to P(k). In strong mathematical induction you are assuming that the statement is true for all values up to k. This is useful in cases where you don't know which value you are going to have to fall back on. Since you have been told to use strong mathematical induction, assume that the statement is true for all integer powers up to and including "n". Then consider n+1 and try to fall back on an arbitrary, small case.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Mar 2010
    Posts
    20
    I understand regular induction, but if since x y and z are all variables and could take any value, how can i consider n+1? For example how does, x^2+y^2=z^(n+1) help when x y and z can take infintely many values and are not constant?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Senior Member
    Joined
    Jul 2010
    From
    Vancouver
    Posts
    432
    Thanks
    17
    You only need to prove existence and in this case infinitely many values can be good! Maybe you can write z in terms of smaller powers?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Mar 2010
    Posts
    20
    Do you mean z^n*z or something like this?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Senior Member
    Joined
    Jul 2010
    From
    Vancouver
    Posts
    432
    Thanks
    17
    Yeap, from what I have tried, this should work, although my solution uses normal and not strong induction.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Newbie
    Joined
    Mar 2010
    Posts
    20
    OK, so does this make sense:

    if n=1, x^2+y^2=z^n is true for x=1, y=2 and z=5
    If n=2, x^2+y^2=z^n is true for x=3, y=4 and z=5

    We assume that this property is true for n=k and all integers less than k
    If we test n=k+1,
    x^2+y^2=z^(k+1)
    x^2+y^2=z^k*z
    If (x^2+y^2)/z^k=z,
    (x^2+y^2)/z^k must be an integer because z is an integer.
    As z is a divisor of z^k, z must also be a divisor of x^2+y^2

    Hence there exists positive integers for which x^2+y^2=z^n for all positive integers of n
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Senior Member
    Joined
    Jul 2010
    From
    Vancouver
    Posts
    432
    Thanks
    17
    I thin you are assuming the conclusion in this line " (x^2+y^2)/z^k must be an integer because z is an integer.".

    This is my initial idea of a proof:

    z^{n+1} = z.z^{n} = z(x^2+y^2) by the inductive hypothesis. Now if z is a square, then z = w^2 for some w. Then z(x^2+y^2) = w^2(x^2+y^2) = (wx)^2+(wy)^2 and the proof is complete. However there is a big problem with this. Can you find it? I think that if you find what is wrong with this proof, you will get a better idea of how to do your proof.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Strong induction vs. structural induction?
    Posted in the Discrete Math Forum
    Replies: 13
    Last Post: April 21st 2011, 01:36 AM
  2. Proof using Strong Mathematical Induction
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: October 12th 2010, 11:36 PM
  3. STRONG induction
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: November 6th 2009, 09:23 PM
  4. Strong induction
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: November 22nd 2008, 02:00 PM
  5. Strong Induction
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: March 5th 2008, 09:50 AM

Search Tags


/mathhelpforum @mathhelpforum