# Prove by induction $\vphantom{\Large A}3\mid\left(n^{3} - n\right)$

So I'm just studying for my midterm and I came across this exercise:

Prove by mathematical induction that $\vphantom{\Large A}3\mid\left(n^{3} - n\right)$ for every positive integer $n$.

What does the pipe symbol "$\mid$" mean? I have never seen it before.

• that pipe symbol means that $3$ divides $n^3-n$... you could have at least showed what you have tried...
– user87543
Dec 4, 2013 at 2:23

If $n = 1$, then $n^3 - n = 0 = 3 \times 0$. So, result holds for the base case. Now let us suppose your statement holdsl for $n \in \mathbb{N}$. In other words, suppose

$$n^3 - n = 3k_0$$

We want to show $(n+1)^3 - (n+1) = 3k_1$ for some $k_1$.

But, Notice

$$(n+1)^3 - (n+1) = n^3 + 3n + 3n^2 + 1 + n - 1 = n^3 - n + 3(n + n^2) + 3k_0 + 3(n + n^2) = 3(k_0 + n + n^2) \cong_3 0$$

Hence, the result follows by mathematical induction.

Note that in this case you have a direct proof:

$n^3-n = n(n^2-1) =n(n-1)(n+1)$ and this is the product of $3$ consecutive integers, so one of them must be divisible by $3$.

Though this is not what you asked, I find it often useful to know more than one proof of a result, because this gives me additional insights which can be useful in other situations.

$a \vert b$ means $a$ divides $b$, i.e., $b$ is a multiple of $a$, i.e., $b = ak$, where $k \in \mathbb{Z}$.
To prove by induction, prove for $n=1$ and note that $$\left((n+1)^3 - (n+1) \right) - \left(n^3 - n\right) = \left(n^3 + 3n^2 + 3n + 1 - (n+1)\right) - n^3 + n = 3n^2 + 3n$$ Now use induction hypothesis to conclude what you want.