Mathematical induction: $9$ divides $n^3 + (n+1)^3 + (n+2)^3$

Question

Prove that $9$ divides $n^3 + (n+1)^3 + (n+2)^3$ where $n$ is a nonnegative integer.

I have seen many questions on this site that contain the answer to this problem and I already know the solution, but I have yet to find offer a clear explanation that I am able to understand. Can somebody please go through this problem and explain step by step as if talking to an elementary school student how it is solved?

I can get this far:

First, show that this is true for n=0: $0^3+(0+1)^3+(0+2)^3=9$

Second, assume that this is true for n: $n^3+(n+1)^3+(n+2)^3=9k$

Third, prove that this is true for n+1: $(n+1)^3+(n+2)^3+(n+3)^3= 9k−n^3+(n+3)^3=$

This is the part that I get lost. Where do we get 9k-n3+(n+3)3? Why wouldn't it just be 9k?

Many thanks in advance for your generous help!

Answer 1

$\underline{\text{Proof by induction:}}$

First, show that this is true for $n=0$:

$0^3+(0+1)^3+(0+2)^3=9$

Second, assume that this is true for $n$:

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

Third, prove that this is true for $n+1$:

$\color{red}{(n+1)^3+(n+2)^3}+(n+3)^3=$

$\color{red}{9k-n^3}+(n+3)^3=$

$9k-n^3+n^3+9n^2+27n+27=$

$9k+9n^2+27n+27=$

$9(k+n^2+3n+3)$

Please note that the assumption is used only in the part marked red.

---

$\underline{\text{Proof by modular-arithmetic:}}$

Consider the following cases:

• $n\equiv0\pmod9\implies n^3+(n+1)^3+(n+2)^3\equiv 0+ 1+ 8\equiv0\pmod9$
• $n\equiv1\pmod9\implies n^3+(n+1)^3+(n+2)^3\equiv 1+ 8+ 27\equiv0\pmod9$
• $n\equiv2\pmod9\implies n^3+(n+1)^3+(n+2)^3\equiv 8+ 27+ 64\equiv0\pmod9$
• $n\equiv3\pmod9\implies n^3+(n+1)^3+(n+2)^3\equiv 27+ 64+ 125\equiv0\pmod9$
• $n\equiv4\pmod9\implies n^3+(n+1)^3+(n+2)^3\equiv 64+125+ 216\equiv0\pmod9$
• $n\equiv5\pmod9\implies n^3+(n+1)^3+(n+2)^3\equiv125+216+ 343\equiv0\pmod9$
• $n\equiv6\pmod9\implies n^3+(n+1)^3+(n+2)^3\equiv216+343+ 512\equiv0\pmod9$
• $n\equiv7\pmod9\implies n^3+(n+1)^3+(n+2)^3\equiv343+512+ 729\equiv0\pmod9$
• $n\equiv8\pmod9\implies n^3+(n+1)^3+(n+2)^3\equiv512+729+1000\equiv0\pmod9$

Please note that this method is handy only when dealing with a relatively small divisor.

Answer 2

For base case $(n=0)$ : $9$ divides $0^3+1^3+2^3=9$.

For inductive step : Supposing that $\color{red}{n^3+(n+1)^3+(n+2)^3=9k}$ where $k\in\mathbb Z$, you need to prove that $(n+1)^3+(n+2)^3+(n+3)^3=9m$ where $m\in\mathbb Z$.

$$\begin{align}\color{red}{(n+1)^3+(n+2)^3}+(n+3)^3&=\color{red}{(9k-n^3)}+(n+3)^3\\&=9k-n^3+n^3+9n^2+27n+27\\&=9(k+n^2+3n+3).\end{align}$$

Answer 3

No induction required to prove that. Write the expression as: $$(n-1)^3+n^ 3+(n+1)^3, \quad n>0$$ instead, i. e. as: $$3n(n^2+2).$$ Now,

• either $n\equiv 0\mod 3$, and $3n\equiv 0\mod 9$;
• or $n\equiv \pm 1\mod 3$, and $n^2+2\equiv 0\mod 3$, so that $3(n^2+1)\equiv 0\mod 9$.

Answer 4

We can always write $n = 3q+r$ where $q$ is a non-negative integer, and $r$ is one of $0$, $1$ and $2$ (this is just division by $3$ with remainder).

Marking all terms which are obviously divisible by $9$ in red and collecting them in a "summary term" $\color{red}{9(\ldots)}$ in the following step, we have $$\begin{align} n^3 + (n+1)^3 + (n+2)^3 &= (3q+r)^3 + (3q+r+1)^3 + (3q+r+2)^2\\ &= \left(\color{red}{(3q)^3} + \color{red}{3(3q)^2r} + \color{red}{3(3q)r^2} + r^3\right) + \\ &\phantom{=} \left(\color{red}{(3q)^3} + \color{red}{3(3q^2)(r+1)} + \color{red}{3(3q)(r+1)^2} + (r+1)^3\right) +\\ &\phantom{=} \left(\color{red}{(3q)^3} + \color{red}{3(3q^2)(r+2)} + \color{red}{3(3q)(r+2)^2} + (r+2)^3\right)\\ &= \color{red}{9(\ldots)} + r^3 + (r+1)^3 + (r+2)^3 \end{align}$$

So we see that we only have to check that $r^2+(r+1)^2+(r+2)^2$ is divisible by $9$. Now on first view this doesn't seem like a win, since this has the exact same form as the expression we started with. But remember that there are only three possible values for $r$, so we can just check directly:

• $r=0$: $r^3 + (r+1)^3 + (r+2)^3 = 0 + 1 + 8 = 9 = 9\cdot 1\quad\checkmark$
• $r=1$: $r^3 + (r+1)^3 + (r+2)^3 = 1 + 8 + 27 = 36 = 9\cdot 4\quad\checkmark$
• $r=2$: $r^3 + (r+1)^3 + (r+2)^3 = 8 + 27 + 64 = 99 = 9\cdot 11\quad\checkmark$

Answer 5

W/O using induction, $$n^3+(n+1)^3+(n+2)^3=3n^3+9n^2+15n+9\equiv3(n^3-n)\pmod9$$

Now $n^3-n\equiv (n-1)n(n+1)$ is a product of three consecutive integers. Exactly one of $n-1,n,n+1$ must be divisible by $3$

Hence, $3|(n^3-n)$