Results 1 to 6 of 6

Math Help - Prove by induction that: n(n^2 + 3n+2) is divisible by 6

  1. #1
    Member
    Joined
    Dec 2008
    From
    Australia
    Posts
    161

    Talking Prove by induction that: n(n^2 + 3n+2) is divisible by 6

    Prove by induction that:  n(n^2 + 3n+2) is divisible by 6, for n>0

    For n =1,
    1(1^2 + 3x1 + 2) = 6
    true for n =1

    assume true for n = k
     k (k^2 + 3k+2) = 6M

    For n = k + 1,
     k [(k+1)^2 + 3(k+1) + 2] should be divisible by 6

    LHS =  k [(k+1)^2 + 3(k+1) + 2]
    =  (k+1) (k^2+5k+6)
    = k(k^2+5k+6) + k^2 + 5k+6
    =  k(k^2 + 3k +2) + 2k^2 + 4k + k^2 + 5k + 6
    = 6M + 3k^2 + 9k + 6
    =  6M + 3(k^2 + 3k +2)
    =  6M + 3(6M/k)
    =  6(M+3/k)

    now I'm stuck. That is obviously not divisible by 6 because M + 3/k is not an integer

    HELP

    Thank you in advance
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Thanks
    2
    Quote Originally Posted by differentiate View Post
    Prove by induction that:  n(n^2 + 3n+2) is divisible by 6, for n>0

    For n =1,
    1(1^2 + 3x1 + 2) = 6
    true for n =1

    assume true for n = k
     k (k^2 + 3k+2) = 6M

    For n = k + 1,
     k [(k+1)^2 + 3(k+1) + 2] should be divisible by 6


    Here it must be (k+1)\left[(k+1)^2+3(k+1)+2\right]

    Tonio


    LHS =  k [(k+1)^2 + 3(k+1) + 2]
    =  (k+1) (k^2+5k+6)
    = k(k^2+5k+6) + k^2 + 5k+6
    =  k(k^2 + 3k +2) + 2k^2 + 4k + k^2 + 5k + 6
    = 6M + 3k^2 + 9k + 6
    =  6M + 3(k^2 + 3k +2)
    =  6M + 3(6M/k)
    =  6(M+3/k)

    now I'm stuck. That is obviously not divisible by 6 because M + 3/k is not an integer

    HELP

    Thank you in advance
    .
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Dec 2008
    From
    Australia
    Posts
    161
    Thank u for the correction, but I still couldn't get it
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Prove It's Avatar
    Joined
    Aug 2008
    Posts
    11,832
    Thanks
    1602
    Quote Originally Posted by differentiate View Post
    Prove by induction that:  n(n^2 + 3n+2) is divisible by 6, for n>0

    For n =1,
    1(1^2 + 3x1 + 2) = 6
    true for n =1

    assume true for n = k
     k (k^2 + 3k+2) = 6M

    For n = k + 1,
     k [(k+1)^2 + 3(k+1) + 2] should be divisible by 6

    LHS =  k [(k+1)^2 + 3(k+1) + 2]
    =  (k+1) (k^2+5k+6)
    = k(k^2+5k+6) + k^2 + 5k+6
    =  k(k^2 + 3k +2) + 2k^2 + 4k + k^2 + 5k + 6
    = 6M + 3k^2 + 9k + 6
    =  6M + 3(k^2 + 3k +2)
    =  6M + 3(6M/k)
    =  6(M+3/k)

    now I'm stuck. That is obviously not divisible by 6 because M + 3/k is not an integer

    HELP

    Thank you in advance
    For n = k you have

     k (k^2 + 3k+2) = 6M

    k(k + 1)(k + 2) = 6M.


    Also, for n = k + 1, you actually have

    LHS = (k + 1)[(k + 1)^2 + 3(k + 1) + 2]

     = (k + 1)(k^2 + 2k + 1 + 3k + 3 + 2)

     = (k + 1)(k^2 + 5k + 6)

     = (k + 1)(k + 2)(k + 3)

     = k(k + 1)(k + 2) + 3(k + 1)(k + 2)

     = 6M + 3(k + 1)(k + 2)


    Now, also notice that (k + 1)(k + 2) is always even.

    So we could write (k + 1)(k + 2) = 2N.


    So you now have

    6M + 3(k + 1)(k + 2) = 6M + 3(2N)

     = 6M + 6N

     = 6(M + N)

    which is divisible by 6.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member
    Joined
    Dec 2008
    From
    Australia
    Posts
    161
    Thanks a bunch Prove It. You're a genius
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Super Member
    Joined
    Aug 2009
    From
    Israel
    Posts
    976
    Just a note - you may prove this in another, easier way, by noting that n(n^2+3n+2)=n(n+1)(n+2) and by using the fact that out of any three consecutive integers, at least one must be divisible by two and another by three, therefore their product has 2*3=6 as a factor and you're done.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. proof by induction 5^n-1 is divisible by 4
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: November 29th 2011, 10:54 AM
  2. Proof by induction: 4^n + 6n + 8 is divisible by 9.
    Posted in the Number Theory Forum
    Replies: 6
    Last Post: April 19th 2011, 05:24 PM
  3. Prove 16^m + 10m -1 is always divisible by 25
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: March 9th 2011, 10:15 AM
  4. Replies: 1
    Last Post: May 8th 2010, 12:49 AM
  5. prove (a^n)-1 is divisible by a-1
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: November 13th 2008, 05:09 PM

Search Tags


/mathhelpforum @mathhelpforum