Question

Prove the following statement by induction. For all nonnegative integers nn, 3 divides n^3 +2n +3n. State the mathematical induction and show your work clearly. 

Answer 1

Let $P(n)$ be the proposition that for all nonnegative integers $n, 3$ divides $n^3 +2n +3.$

BASIS STEP: $P(0)$ is true, because $P(0)=(0)^3+2(0)+3,$ and $3$ divides $3.$

INDUCTIVE STEP: For the inductive hypothesis we assume that $P(k)$ holds for an arbitrary nonnegative integer $k.$ That is, we assume that $3$ divides $k^3 +2k +3, k=0,1,2,...$

Under this assumption, it must be shown that $P(k+1)$ is true, namely, that $3$ divides

$$(k+1)^3 +2(k+1) +3, k=0,1,2,...$$

Note that

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

$$=k^3+3k^2+3k+1+2k+2 +3$$

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

We know that $3$ divides $3(k^2+k+1), k=0,1,2,...$

Then $3$ divides $(k^3+2k+3)+3(k^2+k+1), k=0,1,2,...$ under the assumption that $P(k)$ is true.

This shows that $P(k+1)$ is true under the assumption that $P(k)$ is true. This completes the inductive step.

We have completed the basis step and the inductive step, so by mathematical induction we know that $P(n)$ is true for all nonnegative integers $n.$ That is, we have proven that for all nonnegative integers $n, 3$ divides $n^3 +2n +3.$