# Prove 24 divides $u^3-u$ for all odd natural numbers $u$

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?

-

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$

-
 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. – fridojet Nov 10 '12 at 17:11 +1 ` – fridojet Nov 10 '12 at 17:12

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

-

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

-

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.

-

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.

-
Poster said, "without using complete induction." Not sure what he meant by "complete," but I think he means without induction – Thomas Andrews Nov 9 '12 at 0:52
@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) – Gone Nov 9 '12 at 1:22