Prove that $6$ is a divisor of $n^3 - n$ for all natural numbers. 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}.$$
 A: 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)$.
A: 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$.
A: $ 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
A: Without induction, just note that $n^3 - n = (n+1)n(n-1) = 6\binom{n+1}{3}$.
A: 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
