Prove that $6$ is a divisor of $n^3 - n$ for all natural numbers.

Question

How would you approach such a problem? Induction perhaps? I have been studying proof by induction, but so far I have only solved problems of this nature:

$$1 + 4 + 7 +\dots+ (3n-2) = \frac{n(3n-1)}{2}.$$

Answer 1

You can decompose $n^3-n = (n-1)n(n+1)$. So $n^3-n$ is a product of three consecutive integers, and in such a sequence you always have an even number and a multiple of $3$. Hence $n^3-n$ is a multiple of $6$.

By induction: the base case is $n = 0$, which is trivial. Now suppose $6$ divides $n^3-n$. Claim: $6$ divides $(n+1)^3-(n+1)$. You have $$(n+1)^3-(n+1) =n^3+3n^2+3n+1-n-1=n^3-n+3n(n+1).$$ Now observe that since $6$ divides $n^3-n$ you just need to show that $3n(n+1)$ is a multiple of $6$. But one between $n$ and $n+1$ is even, so $3n(n+1)$ is a multiple of $6$. Hence $6$ divides $(n+1)^3-(n+1)$.

Answer 2

$ P(n) : 6 |(n^3 - n) $

$ P(0) : 6 | 0 $

We assume $ P(k) $ is true and now we demonstrate that $ P(k+1) $ is true

$ P(k) : 6 |(k^3-k) $ that means $ k^3-k=6m $

$ P(k+1) : 6 |((k+1)^3-(k+1)) $

$ P(k+1) : 6 |(k^3+3k^2+2k) $

$ P(k+1) : 6 |(m+3k^2+3k) $

$ P(k+1) : 6 |(m+3k(k+1)) $

$ m $ is divizible by 6 and $ 3k(k+1) $ is divizible by 6 because the product of two consecutive natural numbers is divizible by 2

Answer 3

Without induction, just note that $n^3 - n = (n+1)n(n-1) = 6\binom{n+1}{3}$.

Answer 4

Gibbs has already presented a perfect proof. However, there is another one, that does not involve decomposition of $n^3-n$ and is relatively straightforward.

To say $n^3-n$ is divisible by $6$ is the same as saying $n^3-n \equiv 0 \pmod 6$. Thus, once we compute $n^3-n \pmod 6$ for all possible $n$, we are done. By general algebra, this is the same as computing $n^3-n$ for all elements of the ring $\mathbb Z / 6 \mathbb Z$, and there are exactly $6$ elements in this ring, namely the equivalence classes of $0,1,\dots,5$ modulo $6$.

So, let's compute this $6$ values $\mod 6$:

$$ \begin{array}{ l|c } n & n^3-n \\ \hline 0 & 0-0 \equiv 0 \pmod 6\\ \hline 1 & 1-1 \equiv 0 \pmod 6 \\ \hline 2 & 8-2 \equiv 6 \equiv 0 \pmod 6 \\ \hline 3 & 27-3 \equiv 24 \equiv 0 \pmod 6 \\ \hline 4 & 64 - 4 \equiv 60 \equiv 0 \pmod 6 \\ \hline 5 & 125 - 5 \equiv 120 \equiv 0 \pmod 6 \end{array} $$

As you can see, $n^3-n\equiv 0 \pmod 6$ holds for any $n$.

Answer 5

To prove by induction take the base case $n=0$ or $n=1$.

Then for the inductive step $$(n+1)^3-(n+1)=n^3+3n^2+3n+1-n-1=(n^3-n)+3(n^2+n)$$and the statement will be true if you can show that $n^2+n=n(n+1)$ is even. You can do that various ways, including a similar induction