# 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$