# 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 $\displaystyle n^3 + 3n^2 + 2n$ for every $\displaystyle n > 0$
$\displaystyle S(n)\!:\;\;n^3 + 3n^2 + 2n$ is a multiple of 3.

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

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

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

. . $\displaystyle 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}$

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

. . $\displaystyle (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 $\displaystyle S(k+1)$ . . . The inductive proof is compete.