Results 1 to 7 of 7

Math Help - proof by strong induction

  1. #1
    Member Jskid's Avatar
    Joined
    Jul 2010
    Posts
    160

    proof by strong induction

    My prof is only testing us on the strong form of induction but I can't figure out how to use it with this question.

    Use induction to prove n^3+2n is divisible by 3 for n >= 1.

    Basis
    n_0 = 1 then (1)^3+2(1)=3 which works
    Induction Hypothesis
    Let 1<=l<k and assume l^3+2l is divisible by 3
    Induction Step
    k^3+2k
    ...and now need to use the I.H. somehow
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor Also sprach Zarathustra's Avatar
    Joined
    Dec 2009
    From
    Russia
    Posts
    1,506
    Thanks
    1

    Re: proof by strong induction

    Quote Originally Posted by Jskid View Post
    My prof is only testing us on the strong form of induction but I can't figure out how to use it with this question.

    Use induction to prove n^3+2n is divisible by 3 for n >= 1.

    Basis
    n_0 = 1 then (1)^3+2(1)=3 which works
    Induction Hypothesis
    Let 1<=l<k and assume l^3+2l is divisible by 3
    Induction Step
    k^3+2k
    ...and now need to use the I.H. somehow
    (k+1)^3+2(k+1)=k^3+3k^2+3k+1+2k+2={k^3+2k}+3(k^2+k  +1)
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member Jskid's Avatar
    Joined
    Jul 2010
    Posts
    160

    Re: proof by strong induction

    Quote Originally Posted by Also sprach Zarathustra View Post
    (k+1)^3+2(k+1)=k^3+3k^2+3k+1+2k+2={k^3+2k}+3(k^2+k  +1)
    But k+1 is the week form of induction.
    Or am I confused? I thought the weak form involves let n_0 \le l < k and you assume the statment is true for l and prove that it is for k.
    Last edited by Jskid; November 26th 2011 at 08:57 PM.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member
    Joined
    Aug 2011
    Posts
    127

    Re: proof by strong induction

    Yes, this is "weak" induction, but you don't need "strong" induction for this problem.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member Jskid's Avatar
    Joined
    Jul 2010
    Posts
    160

    Re: proof by strong induction

    Quote Originally Posted by Annatala View Post
    Yes, this is "weak" induction, but you don't need "strong" induction for this problem.
    Can anyone tell me how this would be solved with strong induction?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Member
    Joined
    Aug 2011
    Posts
    127

    Re: proof by strong induction

    Quote Originally Posted by Jskid View Post
    Can anyone tell me how this would be solved with strong induction?
    Do you not realize that strong induction includes weak induction...? The weak induction proof is the strong induction proof, you just don't have to assume as much.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,311
    Thanks
    691

    Re: proof by strong induction

    strong induction lets you assume the hypothesis for any 1 \leq l < k, not just k-1. but, k-1 is indeed < k, so you can use that if you wish.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Strong Induction proof
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: August 24th 2010, 10:01 AM
  2. Proof by strong induction?
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: November 5th 2009, 07:51 AM
  3. Proof Using Strong Induction
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: April 23rd 2009, 10:26 AM
  4. Strong Induction proof
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: November 5th 2008, 12:42 PM
  5. Strong induction proof
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: May 7th 2008, 09:48 PM

Search Tags


/mathhelpforum @mathhelpforum