Proving 3|n³-n

In this post we want to prove that $\forall n \{ n \in \mathbb{N} : 3 | n^{3} - n \}$ .

Proof (by induction): Let $P(n)$ be the predicate that $3 | n^{3} - n$ . It’s trivial to prove $P(0)$ . For the latter, we’re going to assume $P(n)$ . For this proof to work, $P(n) \leftrightarrow P(n+1)$ , so let’s examine the case $P(n+1)$ . This yields $(n+1)^{3} - (n+1) \leftrightarrow n^{3} + 3n^{2} + 3n + 1 - (n+1) \leftrightarrow n^{3} + 3n^{2} + 2n \leftrightarrow (n^{3} - n) + 3n^{2} + 3n$ , which is divisible by three by the induction hypothesis. $\blacksquare$