# Prove by mathematical induction that $n^3 - n$ is divisible by $3$ for all natural number $n$

I'm working on a task where I'm a bit unsure if the answer I've got is correct.

Show by induction that the following assertion is true for all natural numbers $n$

$n^3 - n$ is divisible by $3$

For $n = 1$,
$n^3 - n = 1 - 1$ which is divisible by $3$

Assume the statement is true for some number $n$, that is, $n^3 - n$ is divisible by $3$. Now,

$(n + 1)^3 - (n + 1) = n^3 + 3n^3 + 3n + 1 - n - 1 = (n^3 - n) + 3(n^2 + n)$

which is $n^3 - n$ plus a multiple of $3$.

Since we assumed that $n^3 - n$ was a multiple of $3$, it follows that $(n + 1)^3 - (n + 1)$ is also a multiple of $3$.

So, since the statement "$n^3 - n$ is divisible by $3$" is true for $n = 1$, and its truth for $n$ implies its truth for $n + 1$, the statement is true for all whole number $n$.

I would appreciate if someone could go through the task and the answer and see if I've done this correctly.

Thanks a lot!

-
Yes, it's correct –  user2566092 Oct 20 '13 at 16:41
You are right. But one can prove simplier without induction, if you will consider a decomposition $n^3-n=n(n+1)(n-1)$. –  Boris Novikov Oct 20 '13 at 16:43
To add on to Boris' statement: one of $n-1$, $n$ and $n+1$ must be divisible by three since they are three consecutive integers. –  Cameron Williams Oct 20 '13 at 16:44

$$\pars{n + 1}^{3} - \pars{n + 1} = \pars{n^{3} - n} + 3n\pars{n + 1}$$