# Use mathematical induction to prove that $n^ 3 − n$ is divisible by 3 whenever n is a positive integer.

Solution: Let $P(n)$ be the proposition “$n^3−n$ is divisible by $3$ whenever $n$ is a positive integer”. Basis Step:The statement $P(1)$ is true because $1^3−1=0$ is divisible by $3$. This completes the basis step. Inductive Step:Assume that $P(k)$is true; i.e. $k^3−k$ is divisible by $3$. To complete the inductive step, we must show that when we assume the inductive hypothesis, it follows that $P(k+1)$, the statement that $(k+1)^3− (k+1)$ is divisible by $3$, is also true. That is,we must show that $(k+1)^3− (k+1)$ is divisible by $3$ . $(k+1)^3− (k+1) =(k^3+3k^2+3k+1)-(k+1)$ this where I want to factorize ..need help.

• If you want to factorise, you'd better do it this way: $(k+1)^3-(k+1)=(k+1)((k+1)^2-1)$. – Bernard Masse May 20 '16 at 3:23

In the inductive step we assumed that $k^3 - k$ is divisible by 3 which means that $k^3 - k = 3M$ where $M$ is an integer. Now we can easily deduce $P(k) \rightarrow P(k+1)$. \begin{align} (k + 1)^3 - (k + 1) &= k^3 +3k^2 +3k + 1 -k - 1\\ &= (k^3- k) + 3k^2 + 3k\\ &= 3M +3k^2 + 3k\\ &= 3(M + k^2 + k)\\ &= 3Z \end{align} where $Z = M + k^2 + k$. Since $Z$ is an integer, it is clear $(k + 1)^3 - (k + 1)$ is divisible by 3 if $k^3 - k$ is divisible by 3. Thus concludes the proof.

Now there is a much easier proof that does not require induction, factor $n^3 - n$ as $n(n - 1)(n + 1) = (n - 1)n(n+1)$. Now $n - 1, n$ and $n+1$ are 3 consecutive integers, so one of them must be divisible by 3 since $n \text{ mod } 3$ can take on 3 different values(0, 1 and 2) and the 3 consecutive integers each have a different value, so one of them will be 0 (mod 3). Since one of the integers in the product is divisible by 3, so is the whole product.

• Doesn't $(k+1)^3$ expand out to $k^3 + 3k^2 + 3\boldsymbol{k} +1$? – neurozero Sep 28 '17 at 9:01
• @jct Edited. THanks – Jeevan Devaranjan Sep 29 '17 at 10:00

We get $k^3+3k^2+2k=k(k+1)(k+2)$ because k is an integer and we have a multiplications of 3 sequential integers it is divisible by 3.

Note this does not use induction.

HINT

$((n+1)^3-(n+1))-((n^3)-(n))$

$=3n+3n^2$

• Difference between consecutive numbers is a multiple of 3.. show that first number is a multiple of 3 – N.S.JOHN May 20 '16 at 3:24

BASE Step:-

$n=1$

Then, $n^3-n=1^3-1=0$

And,$3|0$ (Basically any number has the capacity to divide $0$)

ASSUMPTION Step:-

Let us assume that for some Integer $k$, $(n=k)$ it holds i.e. $3|(k^3-k)$

INDUCTIVE Step:-

For the Inductive Step , We have to show the above proposition holds for $n=k+1$ i.e.

$3|(k+1)^3-(k+1)$

So while simplifying We will apply a small trick which makes the problem easy to understand

$(k+1)^3-(k+1)$

$=(k+1){(k+1)^2-1}$

$=(k+1){(k+1-1)(k+1+1)}$

$=(k+1){k(k+2)}$

$=k(k+1)(k+2)$

$=k(k+1)(k-1+3)$

$=(k-1)k(k+1)+3.k(k+1)$

$3|3.k(k+1)$

And by our assumption Step,

$3|(k-1)k(k+1)$

$\Rightarrow 3|k(k+1)(k-1)+3.k(k+1)$

$\Rightarrow 3|(k+1)^3-(k+1)$

We want to prove that when n is an integer, $n^3-n$ is divisible by 3.

To make things easier, we can simply prove the following:

$$(\lfloor n \rfloor ^3 - \lfloor n \rfloor) mod (3)=0$$

Using the formula relating floor to modulo:

$$\lfloor n \rfloor^3 - \lfloor n \rfloor - 3*\lfloor \frac {\lfloor n \rfloor^3 - \lfloor n \rfloor} 3 \rfloor = 0$$

What we need to do is remove the floor on the right term. We shall isolate and work upon it:

let x = floor(n)

$$\lfloor \frac {x(x^2-1)} 3 \rfloor = \lfloor \frac {x(x-1)(x+1)} 3 \rfloor$$

This is where things get tricky. Addition and multiplication by integers is completely splittable within floor. Addition and subtraction is as well. What we want is for that 3 to vanish. This is easily seen by that we have 3 sequential integers. One of them MUST be divisible by 3. However, we cannot show it with algebra. Anyway, the three cancels. Floor is removed, and the equation reduces to 0.

The equation holds true, therefore it is divisible by 3.