Prove using induction that $n^3 − n$ is divisible by $6$ whenever $n > 0$
My attempt:
Base step: For $n=1$
$1^3 – 1 = 0$.
$0$ which is divisible by $6$.
Thus, $n= 1$ is true.
Assumption step: Let $n=k$
$k^3-k$
Inductive step: $f(k+1)-f(k)$
$(k+1)^3-(k+1)-k^3-k$
This is where I am stuck. How do I go forward to prove using induction that $n^3 − n$ is divisible by $6$?
Best Answer
In your assumption step, you need to assume the statement is true for $n=k$, i.e. $k^3-k$ is divisible by $6$.
In the induction step, expand and simplify $(k+1)^3-(k+1)$: $$\begin{aligned}(k+1)^3-(k+1)&=k^3+3k^2+3k+1-k-1\\&=k^3-k+3k^2+3k\\&=(k^3-k)+3k^2+3k\\&=(k^3-k)+3k(k+1)\end{aligned}$$
Note that $k^3-k$ is divisible by $6$ by the inductive hypothesis (the assumption). $k$ and $k+1$ are consecutive integers, so their product must be even. Hence $3k(k+1)$ is also divisible by $6$. Thus, whenever $k^3-k$ is divisible by $6$, we also have that $(k+1)^3-(k+1)$ is divisible by $6$.