# Please verify my induction proof.

I would like to show that the following statement is true by the principle of mathematical induction (I must only use induction, not other theorems to justify my answer)

If $n$ is odd natural number, then $n^3-n$ is divisible by 24.

My proof:

Base Case: For $n=1, n^3-n = 1-1 = 0$ which is divisible by $24$.

Induction hypothesis: Assume that that statement is true for $n=2k-1, k∈N$. This means that $(2k-1)^3 - (2k-1)$ is divisible by 24 and hence $(2k-1)^3 - (2k-1) = 24p, p∈N$.

$(2k-1) [(2k-1)^2-1] = 24p$

$(2k-1)[(2k-1-1)(2k-1+1)] = 24p$

$(2k-1)[(2k-2)(2k)] = 24p$

$8k^3-12k^2+4k=24p$

Inductive step: Show that the statement is true for $n=2k+1, k∈N$.

$n^3-n = (2k+1)^3-(2k+1)$

$= (2k+1)[(2k+1)^2-1]$

$=(2k+1)[(2k+1-1)(2k+1+1)]$

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

$=8k^3+12k^2+4k$

$=(8k^3-12k^2+4k)+24k^2$

$=24p+24k^2$ (Induction hypothesis)

$=24(p+k^2)$

Both expressions are divisible by $24$, hence the expression is divisible by 24.

We have shown that the statement is true for $n=2k+1$. Therefore, by induction, statement is true for all odd natural numbers n.

• Seems fine to me – RGS Nov 24 '16 at 23:18
• Your proof is right but there is a little mistake. It should be $(2k-1)(2k-2)(2k)=24p$. – Xam Nov 24 '16 at 23:24
• There is a tiny thing in your proof: $(2k-1)^2-1=4k^2-4k=4k(k-1)\neq (2k-1)2k$ – Ruzayqat Nov 24 '16 at 23:27
• @Ruzayqat where? – mathewconway Nov 24 '16 at 23:30
• okay, corrected @Charter – mathewconway Nov 24 '16 at 23:33

That's the right idea. Essentially you have verified the following equation

$$\color{}{(2k+1)^3 -(2k+1)}\, =\ \color{#0a0}{(2k-1)^3 - (2k-1)}\, +\, 24k^2$$

Therefore $\ 24\mid \color{#0a0}{\rm green}\,\Rightarrow\,24\mid\rm RHS\,\Rightarrow\,24\mid LHS,\,$ which yields the inductive step.

Remark $\$ A slicker way to prove that equality is to note that $\,f(k) = \rm RHS-LHS$ is at most quadratic (cubic terms cancel), so to verify that it is zero it suffices to show that it has $3$ roots, e.g. verify $\,0 = f(1) = f(2) = f(3).\,$ But this looks like the base of an inductive proof! Indeed, if you study the calculus of finite differences and/or telescopy you will learn even nicer ways to handle such inductive proofs. You can find some examples in my posts on telescopy.

• Nice job, Bill (really)! I like how you address the OP's question and also enriched it! – Namaste Nov 24 '16 at 23:49

Induction is not necessary.

$n^3-n=(n-1)n(n+1)$, so at least one of them is multipe of 3.

In addition, if $n$ is odd, both $n-1$ and $n+1$ are even. In fact one of then must be multiple of 4, so $(n-1)(n+1)$ is multiple of 8.

Hence, $n^3-n$ is multiple of 24.

• @amWhy, relax, Tito isn't hurting anyone, jeez. Also, your quote from the question is actually an addition made by Bill after Tito already answered. – tilper Nov 25 '16 at 0:18
• @tilper I'm relaxed. I didn't know that the sentence I quoted was edited in, after it's post. Tito's observations are fine (note, I did not nor will I downvote this answer). I just really hope that when a questioner asks whether their procedure/proof/solution is correct, that any answerer address that question first. The best then go on to also include alternative approaches, or how to simplify the OP's approach, etc. – Namaste Nov 25 '16 at 0:24