1
$\begingroup$

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.

Please give me your suggestions. Thanks!

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

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.

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

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.

$\endgroup$
  • $\begingroup$ @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. $\endgroup$ – tilper Nov 25 '16 at 0:18
  • $\begingroup$ @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. $\endgroup$ – Namaste Nov 25 '16 at 0:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.