Proof that $n^3-n$ is a multiple of $3$. I'm struggling with this problem of proof by induction:
For any natural number $n$, prove that $n^3-n$ is a multiple of $3$.

I assumed that $k^3-k=3r$
I want to show that $(k+1)^3-(K+1)=3r$
The final statement is $K^3 +3K^2+2K$
Am I missing something ?
 A: $n^3-n = (n+1)n(n-1).$ The right hand side is a product of three consecutive integers... For a proof by induction,  note that $(n+1)^3-(n+1) - n^3 + n = 3n^2 + 3 n,$ which is obviously divisible by $3.$ So, if you prove the statement for $n=0,$ you are good to go.
A: If you have $k^3-k$ divisible by 3, then look at $$(k+1)^3-(k+1)=k^3+3k^2+2k = $$ and this is where you need to spot you can use the inductive hypothesis, because you have a $k^3$ there $$=(k^3-k)+3k^2+3k$$ and the term which doesn't have a coefficient $3$ is divisible by $3$ by the hypothesis.
A: Use Fermat's little theorem.
Case1: if n is a multiple of 3 then trivially $n^3 -n$ is a multiple of $3$.
Case 2: If $n$ is not a multiple of $3$ you shall get $n^2 \equiv 1 \pmod 3$. Multiply $n$ and get $n^3 -n \equiv 0 \pmod 3$.
Now get your result.
A: If you want induction, here you go :
$k^3-k=3m$
$(k+1)^3-(k+1)=k^3+3k^2+3k+1-k-1=(k^3-k)+3(k^2+k)=3m+3n=3(m+n)$
This should help you i guess..
A: If $n=0 \mod 3$ then is nothing to prove. 
Suppose that $(n,3)=1.$
Now it follows from the  Ferma litle theorem. We  have  that $n^3=n \mod 3$  or, in other words, $n^3-n$ is multiple of 3. 
A: using congruence theory we can make easier our steps. Note that if we show $n^3\equiv n [3]$ then we are done. Cause in that case, we shall have $3|n^3-n$ which was asked to prove.
Now any positive integer $n$ gives 0, 1, 2 as remainder when divided by 3. In other words, $n\equiv 0, 1, 2[3]$.
When $n\equiv 0[3]$ then evidently $n^3\equiv 0\equiv n[3]$ so that $n^3\equiv n[3]$ is done.
When $n\equiv 1[3]$ then $n^3\equiv 1[3]$ and hence $n^3-n\equiv 1-1\equiv 0[3]$ so that $n^3\equiv n[3]$ again holds. Finally when $n\equiv 2\equiv -1[3]$ then $n^3\equiv -1[3]$ and then $n^3-n\equiv (-1)-(-1)\equiv 0[3]$ so that $n^3\equiv n[3]$ holds.
Thus we can see that no matter whatever $n\in\mathbb{N}$ we choose we shall always have $n^3\equiv n[3]$ in otherwords $3|n^3-n$.
Done
