Proving a Statement using Mathematical Induction

Question

I'm trying to prove that $6 \mid (n^3 - n)$ where $n$ is a nonnegative integer. I started off by proving the basic step with $P(6)=4$. The next step would be the induction. However I'm having a bit f trouble understanding and using the method. Could someone show me how I would prove the statement and explain to me how I would get the answer. Thanks in advance.

Answer 1

Hint $\ $ Let $\,f(n) = n^3-n\,$ The base case is clear $\,6\mid f(0) = 0.\ $ For the inductive step we need to prove that $\,6\mid f(n)\,\Rightarrow\, 6\mid f(n\!+\!1).\,$ For this it suffices to prove that $\,6\,\mid f(n\!+\!1)-f(n)=: g(n)\,$ since then $\,6\mid g(n),f(n)\,\Rightarrow\,6\mid g(n)+f(n) = f(n\!+\!1).\ $ But this is easy

$$ f(n\!+\!1) - f(n)\, =\, (n\!+\!2)\color{#0a0}{(n\!+\!1)n - (n+1)n}(n-1) \,=\, 3\color{#0a0}{n(n+1)}$$

which is divisible by $6$ since $\,n\,$ or $\,n\!+\!1\,$ is even (or, use the same method recursively: note that for $\,p(n) = n(n\!+\!1)\,$ we have $\,2\mid p(0)\,$ and $\,2\mid p(n\!+\!1)-p(n) = 2(n\!+\!1))\,$

Remark $\ $ This is a special case of a powerful general method known as telescopic induction. You can find many more examples in my posts on telescopy.

Answer 2

The statement $P(n)$ you are trying to prove should be

$6$ divides $n^3-n$

and your base case should be $P(0)$, which is

$6$ divides $0^3-0$.

The induction step will be to prove

If $P(n)$ is true, then $P(n+1)$ is also true

which is

If $6$ divides $n^3-n$, then $6$ divides $(n+1)^3-(n+1)$

Answer 3

Though this can be proven far more easily without induction, but since you asked for it, here goes...
$$P(1)=1^3-1=0$$
Also,
$6|0$ this implies $P(0)$ is true.
Let $P(n)$ be true for all positive integers.
We now have to prove that $P(n+1)$ is true.
$$P(n+1)=(n+1)^3-(n+1)=n^3+3n^2+2n$$
Furthermore, we can write
$$n(n^2+3n+2)=n(n+1)(n+2)$$
We now essentially have to prove that the product of three consecutive natural numbers is divisible by $6$.
Since $P(n+1)$ just equals the product of three consecutive integers we can see that this will be divisible by $6$ as they can be written as $x(2y)(3z)$ or $x(6y)z$.
This is because there has to be a number divisble by $3$ and another one divisble by $2$ in $3$ consecutive integers. However the same number can be divisible by both. Hence the second case.
Hence proved (by induction).

Answer 4

Special of this answer is that only uses induction. It is not taken for granted that the product of two consecutive numbers is even.

Let $P\left(n\right)$ denote the statement:

$2\mid n\left(n+1\right)$ and $6\mid n^{3}-n$

We will prove by induction that $P(n)$ is true for each nonnegative integer $n$.

It is evident that $P\left(0\right)$ is true: $2\mid0=0\left(0+1\right)$ and $6\mid0=0^{3}-0$.

Assume that $P\left(n\right)$ is true for some nonnegative integer $n$.

To be shown is now that $P\left(n+1\right)$ is true, i.e. that $2\mid\left(n+1\right)\left(n+2\right)$ and $6\mid\left(n+1\right)^{3}-\left(n+1\right)$.

$\left(n+1\right)\left(n+2\right)=n\left(n+1\right)+2\left(n+1\right)$ where $2\mid n\left(n+1\right)$ is true and where of course also $2\mid2\left(n+1\right)$. So we conclude that $2\mid\left(n+1\right)\left(n+2\right)$.

$\left(n+1\right)^{3}-\left(n+1\right)=n^{3}-n+3n\left(n+1\right)$ where $6\mid n^{3}-n$ and also $6\mid3n\left(n+1\right)$ as a direct consequence of $2\mid n\left(n+1\right)$. So we conclude that $6\mid\left(n+1\right)^{3}-\left(n+1\right)$.

Proved is now purely by induction that $P\left(n\right)$ is true for each nonnegative $n$. This implies that $6\mid n^{3}-n$ for each $n$.