Help with induction proof please! For an integer $n, 3$ divides $n^3-n$

Question

Please help with this induction proof! I am trying to show that for an integer $n, 3$ divides $n^3-n$. I know how to do it for all positive integers, but am not sure how to prove it for 0 or negative integers.

Answer 1

If $n^3-n=3q$ we have \begin{eqnarray} (n+1)^3-(n+1)&=&(n+1)(n^2+2n+1)-n-1\\ &=&n^3+2n^2+n+n^2+2n+1-n-1\\ &=&(n^3-n)+3n^2+3n \end{eqnarray}

Answer 2

Guide to perform induction for non-positive number:

Base case: show that the statement is true for $n=0$.

Induction step: Suppose the statement is true for $n=k$, then show that the statement is true for $n=k-1$ too, that is if $k^3-k$ is divisible by $3$, then show that $(k-1)^3-(k-1)$ is divisible by $3$.

The working should be highly similar to the positive number case.

Hence, if the statement is true for $n=0$, using the induction step, we can conclude that it is true for $n=-1$, $n=-2, \ldots.$

Answer 3

Problem: Prove that $n^3-n$ is divisible by $3$.

Solution: Let $f(n)$ denote the statement

$$f(n)=n^3-n$$

Base Step ($n=1$): \begin{align} f(1) & = 1^3-1 \\ & = 0 \end{align} $3 | 0 \implies f(1)$ holds.

Inductive Step $f(k) \to f(k+1)$: Fix some $k$. Assume that $$f(k)=k^3-k$$ holds and is divisible by $3$. To be proved is that $$f(k+1)=(k+1)^3-(k+1)$$ follows. Beginning with the right-hand side of $f(k+1)$

\begin{align} (k+1)^3-(k+1) & = k^3+3k^2+3k+1-k-1\\ & = k^3+3k^2+2k \\ & = k^3-k+3k^2+3k \\ & = f(k) + 3(k^2+k) \end{align}

by the inductive assumption, $3|f(k)$. Clearly, $3|3(k^2+k)$, thereby showing $f(k+1)$ is true, completing the inductive step.

Conclusion: By mathematical induction, it is proved that $n^3-n$ is divisible by $3$. $\Box$