Use induction to prove that $6$ divides $n^3 - n$.

Question

This is somewhat embarrassing, but I am having some trouble figuring out how to do a strong induction question. We have to prove that $n^3 - n$ is divisible by $6$ for all $n \in \mathbb{N}$. Now I can see that this must be true, since $n^3 - n = (n+1)n(n-1)$, i.e. the product of three consecutive integers. Therefore at least one of them will be even, and one will be a multiple of $3$. Hence the product will be divisible by $6$. However, I can't figure out how to do it by induction. It's probably quite easy to do once you see one of those trick moves, like adding and subtracting the same thing, etc, but I can't figure it out. Please help!

Answer 1

As $n^3$ and $n$ are both even or both odd, $n^3-n$ is always even. Hence it is enough to show $n^3-n$ is divisible by $3$.

This of course is just Lil' Fermat, since $3$ is prime. But it's easy to prove it by induction: $$(n+1)^3-(n+1)=(n^3-n)+3n^2+3n$$ from which it follows at once.

Answer 2

Base case holds: $6|1-1$.

For induction step:

Assume that $6|n^3-n$.

We have $$(n+1)^3-(n+1)=(n^3-n)+3n^2+3n=(n^3-n)+3n(n+1).$$ By induction assumption $6|n^3-n$.

Also, $$2|n(n+1),$$ since product of two consecutive numbers is divisible by $2$.

(Induction proof of the previous fact: $2|1*2$, so induction base holds. Induction step: assume $2|n(n+1)$, write $(n+1)(n+2)=n(n+1)+2(n+2)$ and conclude from that: $2|(n+1)(n+2)$.)

Therefore, $$6|3n(n+1).$$ Summing those two gives $$6|(n+1)^3-(n+1).$$