# need help with induction prove..

• Feb 16th 2008, 07:51 AM
st4rl1ight
need help with induction prove..
How do you prove this?
Use induction to prove that 3 divides n^3 + 3n^2 + 2n for every nonnegative integer n.
• Feb 16th 2008, 09:13 AM
Soroban
Hello, st4rl1ight!

Quote:

Use induction to prove that 3 divides $n^3 + 3n^2 + 2n$ for every $n > 0$
$S(n)\!:\;\;n^3 + 3n^2 + 2n$ is a multiple of 3.

Verify $S(1)\!:\;\;1^3 + 3\!\cdot\!1^2 + 2\!\cdot\!1 \:=\:6\:=\:3(2)$ . . . true!

Assume $S(k)\!:\;\;k^3 + 3k^2 + 2k \:=\:3a$ for some integer $a.$

Add $(3k^2 + 3k + 1)+(6k+3) + 2$ to both sides:

. . $k^3 \;{\color{blue}+ \;3k^2 + 3k + 1} + \;3k^2 \;{\color{blue}+ \;6k + 3} \;+\; 2k \;{\color{blue}+\; 2} \;=\;3a \;+ \;{\color{blue}(3k^2 + 3k + 1) + (6k+3) + 2}$

$\text{And we have: }\;(k^3 + 3k^2 + 3k + 1) \;+\;3(k^2 + 2k +1) \;+ \;2(k+1) \;=\;3a \;+ \;3k^2 \;+ \;9k \;+ \;6$

. . $(k+1)^3 + 3(k+1)^2 + 2(k+1) \;=\; \underbrace{3\left(a + k^2 + 3k + 2\right)}_{\text{a multiple of 3}}$

We have proved $S(k+1)$ . . . The inductive proof is compete.