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

• Nov 13th 2009, 05:14 PM
differentiate
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

• Nov 13th 2009, 05:22 PM
tonio
Quote:

Originally Posted by differentiate
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

.
• Nov 13th 2009, 05:27 PM
differentiate
Thank u for the correction, but I still couldn't get it
• Nov 13th 2009, 05:28 PM
Prove It
Quote:

Originally Posted by differentiate
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

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.
• Nov 13th 2009, 05:35 PM
differentiate
Thanks a bunch Prove It. You're a genius
• Nov 14th 2009, 03:20 AM
Defunkt
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.