8
$\begingroup$

At our college, a professor told us to prove by a semi-formal demonstration (without complete induction):

  • For every odd natural: $24\mid(u^3-u)$

He said that that example was taken from a high school book - maybe I din't get something, but I really have no idea to prove that without using complete induction.

Any idea of smart demonstration?

Thanks for your help. (Excuse my bad English.)

$\endgroup$
19
$\begingroup$

First note that $$ u^3-u = (u-1)u(u+1)$$

Given that $u$ is odd.In this case, $u-1$ and $u+1$ are even and one of them is divisible by 4. This follows from the basic observation that one of any two consecutive even numbers is divisible by 4. So, $(u-1)(u+1)$ is divisible by $4 \times 2 =8$.

Also, one of any three consecutive natural numbers is divisible by 3. So, one of $u-1,u,u+1$ is divisible by 3.

So, $(u^3-u)$ is divisible by 8 and 3, which are co-prime. So, it is divisible by $8\times 3=24$

$\endgroup$
  • $\begingroup$ I have recently got this solution from a friend of mine who was able to help me. But much thanks anyway for this really nice explanation. $\endgroup$ – fridojet Nov 10 '12 at 17:11
  • $\begingroup$ +1 ``````````````````````````` $\endgroup$ – fridojet Nov 10 '12 at 17:12
14
$\begingroup$

Factor it: $u^3-u=u(u^2-1)=u(u-1)(u+1)$. Now show that one of the three factors must be divisible by $4$ and another by $2$, and that one must be divisible by $3$.

$\endgroup$
6
$\begingroup$

Observe that $u^3-u=(u-1)u(u+1)$. Now $3$ consequtive numbers are always divisible by $3$. So $3\mid u^3-u.$ Since $u$ is odd $\Rightarrow$ $u-1, \ u+1$ are even. Prove that one of $u-1, \ u+1$ is divisible by $4$ and the other by $2$. Conclude that $24\mid u^3-u.$

$\endgroup$
5
$\begingroup$

Another proof.

I assume you know the following formula:

$$1^2+2^2+...+k^2 = \frac{k(k+1)(2k+1)}{6}$$

for all integer $k\geq 0$.

If $u$ is odd then $u=2k+1$ for some integer $k\geq 0$. Expanding:$$u^3-u = (2k+1)^3-(2k+1) = 8k^3 + 12k^2 + 6k + 1 - (2k+1) = 8k^3 + 12k^2 + 4k \\= 4k(2k+1)(k+1)=24\frac{k(k+1)(2k+1)}{6}$$

So if $u$ is odd, then $\frac{u^3-u}{24}$ is the sum of the first $k=\frac{u-1}{2}$ squares, and hence is an integer.

$\endgroup$
1
$\begingroup$

Hint $ $ Induction step: $\rm\:24\:|\:f(n) = n^3\!-n\:\Rightarrow\:24\:|\:f(n\!+\!2) = f(n) + 6(n\!+\!1)^2\:$ by $\rm\:n\!+\!1\:$ is even.

Remark $\ $ If we telescsope this we obtain a nice representation showing the factor of $24$.

$$\rm\begin{eqnarray} f(2n\!+\!1)\! -\! f(1)\, &=&\,\rm f(2n\!+\!1)\!&&\rm-\ f(2n\!-\!1) &&\rm+\ \,\cdots\, + f(5)\!&&\rm-\ f(3) &&\rm +\ \ f(3)\!&&\rm-\ f(1) \\ \,&=&\,\rm &&\!\!\!\!\!\rm6(2n)^2&&+\ \,\cdots\, + &&\!\!\!6\cdot4^2&& +&&\!\!\!6\cdot2^2\end{eqnarray}$$

So, using $\rm\:f(1) = 0,\:$ and pulling out a factor of $\,4\,$ from the RHS via $\rm\,(2k)^2 = 4\cdot k^2$ we obtain

$$\rm\ f(2n\!+\!1)\, =\, 24\, (n^2 + (n\!-\!1)^2 +\, \cdots\, + 2^2 + 1^2)$$

making the factor of $24$ clear. This is essentially the result in Thomas's answer except that we have derived it mechanically (requiring no insight or special knowledge), using only the very simple idea of telescopy - about which you can find much more written in many of my prior posts on telescopy.

$\endgroup$
  • 1
    $\begingroup$ Poster said, "without using complete induction." Not sure what he meant by "complete," but I think he means without induction $\endgroup$ – Thomas Andrews Nov 9 '12 at 0:52
  • $\begingroup$ @Thomas But your answer is essentially the same as this - see my added remark. "Without induction" is meaningless, does a proof not "use induction" if it invokes a lemma that uses induction? (as you do) $\endgroup$ – Bill Dubuque Nov 9 '12 at 1:22
1
$\begingroup$

Here is a slightly different proof, showing $u(u^2 - 1)$ is divisible by $24$ when $u$ is odd.

Since $u$ is odd, $u$ is of the form $2k + 1$, where $k$ is an integer.
Rewriting, we have: $$(2k + 1)((2k + 1)^2 - 1)$$ $$(2k + 1)(4k^2 + 4k)$$ $$(2k + 1)4k(k + 1)$$ Let $m$ denote this last expression.

Every integer (and thus $k$) is of one of the three forms: $3q$, $3q - 1$, or $3q - 2$, where $q$ is an integer.

Case $k$ = $3q$:
$k$ is divisible by $3$ and either $k$ or $k + 1$ is even (and thus divisible by $2$).
Thus $m$ is of the form $4(3)(2)h$ = $24h$ and therefore divisible by $24$.

Case $k$ = $3q - 1$:
$k + 1$ is divisible by $3$ and either $k$ or $k + 1$ is even (and thus divisible by $2$).
Thus $m$ is of the form $4(3)(2)h$ = $24h$ and therefore divisible by $24$.

Case $k$ = $3q - 2$:
$2k + 1$ = $6q - 3$ is divisible by $3$ and either $k$ or $k + 1$ is even (and thus divisible by $2$).
Thus $m$ is of the form $4(3)(2)h$ = $24h$ and therefore divisible by $24$.

Q.E.D.

$\endgroup$

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.