# 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
– Martin Sleziak Jan 5 at 13:35

$\newcommand{\angles}[1]{\left\langle #1 \right\rangle}% \newcommand{\braces}[1]{\left\lbrace #1 \right\rbrace}% \newcommand{\bracks}[1]{\left\lbrack #1 \right\rbrack}% \newcommand{\dd}{{\rm d}}% \newcommand{\isdiv}{\,\left.\right\vert\,}% \newcommand{\ds}[1]{\displaystyle{#1}}% \newcommand{\equalby}[1]{{#1 \atop {= \atop \vphantom{\huge A}}}}% \newcommand{\expo}[1]{\,{\rm e}^{#1}\,}% \newcommand{\ic}{{\rm i}}% \newcommand{\imp}{\Longrightarrow}% \newcommand{\pars}[1]{\left( #1 \right)}% \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}} \newcommand{\pp}{{\cal P}}% \newcommand{\sgn}{\,{\rm sgn}}% \newcommand{\ul}[1]{\underline{#1}}% \newcommand{\verts}[1]{\left\vert #1 \right\vert}% \newcommand{\yy}{\Longleftrightarrow}$
$$\pars{n + 1}^{3} - \pars{n + 1} = \pars{n^{3} - n} + 3n\pars{n + 1}$$