# Show that $n^3-n$ is divisible by $6$ using induction

As homework, I have to prove that

$\forall n \in \mathbb{N}: n^3-n$ is divisible by 6

I used induction

1) basis: $A(0): 0^3-0 = 6x$ , $x \in \mathbb{N}_0$ // the 6x states that the result is a multiple of 6, right?

2) requirement: $A(n):n^3-n=6x$

3) statement: $A(n+1): (n+1)^3-(n+1)=6x$

4) step: $n^3-n+(n+1)^3-n=6x+(n+1)^3-n$

So when I resolve that I do get the equation: $n^3-n=6x$ so the statement is true for $\forall n \in \mathbb{N}$

Did I do something wrong or is it that simple?

• I know what you meant, but it's confusing when in both of steps (2) and (3) you use $6x$. It would be clearer if you had said in (2) $n^3-n=6x$ for some integer $x$ and in (3) you had said $(n+1)^3-(n+1)=6y$ for some integer $y$. – Rick Decker Oct 11 '12 at 15:40

No, your argument is not quite right (or at least not clear to me). You must show that if $A(n)$ is true, then $A(n+1)$ follows. $A(n)$ here is the statement "$n^3-n$ is divisible by $6$". Assuming $A(n)$ is true, then $$(n+1)^3-(n+1)=n^3+3n^2+3n+1-n-1=(n^3-n)+3n(n+1)$$ is divisible by $6$ because (1) $n^3-n$ is a multiple of $6$ by assumption, and (2) $3n(n+1)$ is divisible by $6$ because one of $n$ or $n+1$ must be even (this is related to what Alex was pointing out). Therefore $A(n)$ implies $A(n+1)$ and, if $A(n)$ is true for some value of $n$, then all higher integer values of $n$ follow. You correctly showed that $A(0)$ is true.

• Of course, the argument that "one of $n$ or $n+1$ must be even" is no different from "one of $n, n-1, n+1$ must be divisible by 3". To stay within the spirit of the problem, the fact that $3n(n+1)$ is divisible by 6 should also be proved by induction. – mathguy Aug 1 '16 at 13:33

No need for induction. $$n^3-n=n(n^2-1)=n(n-1)(n+1)$$ which are three consecutive integers. So one must be divisible by 3.

Check for $n=1$: $1^3-1=0=3\cdot 0$

Assume it's true for $n=k$. If you let $n=k+1$ you get \begin{align*} (k+1)^3-(k+1)&=k^3+3k^2+2 \\ &=k^3+3k^2+2k\\ &=3\cdot (k^2+k)+(k^3-k)\end{align*} which is divisible by 3

• Thank you for your answer. I know that way, but I wanted to know if I used the principle of induction in the correct way. – Marco Rauscher Oct 11 '12 at 14:54
• @Alex There is a need for induction if the question says "prove by induction" (as has been known to happen on a test). – yroc Nov 23 '15 at 19:59

If $n^3-n=6m$,

$$(n+1)^3-(n+1)=n^3+3n^2+2n=6m+3(n^2+n).$$

Then, by an auxiliary induction $n^2+n$ is even.

Indeed, $0^2+0$ is even and if $n^2+n=2k$,

$$(n+1)^2+(n+1)=n^2+3n+2=2k+2(n+1)$$ which is even.

Finally, $3$ times an even number is a multiple of $6$.

Proof,

$$6 | (n³ - n) , n ≥ 2$$

Base Case:
If, $$n = 2$$ Then $$n³- n = 2³ -2 = 8 - 2 = 6$$ And 6 | 6, because 6 (1) = 6

Inductive Hypothesis:
Suppose: $$6 | k³ - k$$
Therefore, $$6 | (k+1)³ - (k+1)$$
$$(k + 1)³ - (k + 1) = k³ + 3k² + 3k + 1 - k -1$$ $$= (k³ - k) + (3k² + 3k) = (k³- k) + 3k(k + 1)$$
So we know that 6 | k³- k, because that's what we supposed in the IH.
However, 3k(k+1) must have its own proof.

So,

$$6 | 3n (n + 1)$$

Base Case:
If $$n = 2$$ Then $$3n (n + 1) = 3(2) (2 + 1) = 6 (3) = 18$$

And 6 | 18, because 6 (3) = 18

Inductive Hypothesis:
Suppose: $$6 | 3k (k + 1)$$
Therefore, $$6 | 3 (k + 1) (k + 2)$$

$$3 (k + 1) (k + 2) = 3k² + 9k + 6 = 3k² + 6k + 3k + 6$$ $$= (3k² + 3k) + (6k + 6) = 3k (k + 1) + 6 (k + 1)$$
So we know that 6 | 3k (k + 1), because that's what we supposed in the IH.
And we know that 6 | 6 (k + 1) by definition.

That means that $$6 | 3k(k+1)$$.

Therefore, we can say that $$6 | (k + 1)³ - (k + 1)$$

This answer is with basic induction method...

when n=1, $$\ 1^3-1 = 0 = 6.0$$

is divided by 6. so when n=1,the answer is correct.

we assume that when n=p , the answer is correct

so we take, $$\ p^3-p$$ is divided by 6.

then, when n= (p+1),

$$\ (p+1)^3-(p+1) = (P^3+3p^2+3p+1)-(p+1)$$ $$\ =p^3-p+3p^2+3p+1-1$$ $$\ =(p^3-p)+3p^2+3p$$ $$\ =(p^3-p)+3p(p+1)$$

as we assumed $$\ (p^3-p)$$ is divided by 6.

$$\ 3p(p+1)$$ is divided by 3 and as P is a positive integer, P(p+1) is divided by 2, [as n(n+1) is the formula of even numbers].

so 3p(p+1) is divided by 6 too.

so that $$\ =(p^3-p)+3p(p+1)$$ is divided by 6.

hence, the answer is correct when n=p+1. When n=p the answer is correct too. We proved that the answer is correct when n=1. so as the mathematical induction,
$$\ n^3-n$$ is divided by 6 for the all positive integers.