Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question

5 Answers 5

up vote 15 down vote accepted

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$

share|improve this answer
    
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$.

share|improve this answer

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

share|improve this answer

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.

share|improve this answer

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.

share|improve this answer
1  
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) –  Bill Dubuque Nov 9 '12 at 1:22

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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