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.)

6 Answers 6

19

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$

  • 0
    +1 ```````````````````````````2012-11-10
14

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$.

6

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.$

5

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.

1

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.

  • 0
    @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)2012-11-09
1

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.