TAOCP 1.2.1 Exercise 8
We prove by induction that for every positive integer $n$, n^3=(n^2-n+1)+(n^2-n+3)+\cdots+(n^2-n+(2n-1)).
Section 1.2.1: Mathematical Induction
Exercise 8. ▶ [25] (a) Prove the following theorem of Nicomachus (A.D. c. 100) by induction: $1^3 = 1$, $2^3 = 3 + 5$, $3^3 = 7 + 9 + 11$, $4^3 = 13 + 15 + 17 + 19$, etc. (b) Use this result to prove the remarkable formula $1^3 + 2^3 + \cdots + n^3 = (1 + 2 + \cdots + n)^2$.
[Note: An attractive geometric interpretation of this formula, suggested by Warren Lushbaugh, is shown in Fig. 5; see Math. Gazette 49 (1965), 200. The idea is related to Nicomachus’s theorem and Fig. 3. Other “look-see” proofs can be found in books by Martin Gardner, Knotted Doughnuts (New York: Freeman, 1986), Chapter 16; J. H. Conway and R. K. Guy, The Book of Numbers (New York: Copernicus, 1996), Chapter 2.]
$$ \begin{aligned} \text{Side} &= 5 + 5 + 5 + 5 + 5 + 5 = 5 \cdot (5 + 1) \ \text{Side} &= 5 + 4 + 3 + 2 + 1 + 1 + 2 + 3 + 4 + 5 \ &= 2 \cdot (1 + 2 + \cdots + 5) \ \text{Area} &= 4 \cdot 1^2 + 4 \cdot 2 \cdot 2^2 + 4 \cdot 3 \cdot 3^2 + 4 \cdot 4 \cdot 4^2 + 4 \cdot 5 \cdot 5^2 \ &= 4 \cdot (1^3 + 2^3 + \cdots + 5^3) \end{aligned} $$
[Figure 5] A geometric grid visualization
Fig. 5. Geometric version of exercise 8(b).
Verified: yes
Solve time: 1m58s
Solution
(a) Nicomachus's theorem
We prove by induction that for every positive integer $n$,
$$ n^3=(n^2-n+1)+(n^2-n+3)+\cdots+(n^2-n+(2n-1)). $$
In other words, $n^3$ is the sum of $n$ consecutive odd integers beginning with $n^2-n+1$.
Let $P(n)$ denote this statement.
Base case
For $n=1$,
$$ 1^3=1, $$
and the formula gives
$$ 1^2-1+1=1. $$
Thus $P(1)$ is true.
Inductive step
Assume that $P(k)$ holds. Then
$$ k^3=(k^2-k+1)+(k^2-k+3)+\cdots+(k^2-k+(2k-1)). $$
We must prove $P(k+1)$.
The claimed block for $(k+1)^3$ is
$$ S=(k^2+k+1)+(k^2+k+3)+\cdots+(k^2+k+(2k+1)). $$
There are $k+1$ terms in this sum. Write each term as
$$ (k^2-k+(2i+1))+2k, \qquad 0\le i\le k. $$
Separating the last term gives
$$ \begin{aligned} S &=\sum_{i=0}^{k-1}\bigl((k^2-k+(2i+1))+2k\bigr) +\bigl((k^2-k+(2k+1))+2k\bigr)\ &=\sum_{i=0}^{k-1}(k^2-k+(2i+1)) +2k\cdot k +(k^2+k+1). \end{aligned} $$
By the inductive hypothesis,
$$ \sum_{i=0}^{k-1}(k^2-k+(2i+1))=k^3. $$
Therefore
$$ \begin{aligned} S &=k^3+2k^2+(k^2+k+1)\ &=k^3+3k^2+3k+1\ &=(k+1)^3. \end{aligned} $$
Hence $P(k+1)$ holds.
By mathematical induction, for every positive integer $n$,
$$ n^3=(n^2-n+1)+(n^2-n+3)+\cdots+(n^2-n+(2n-1)). $$
This is Nicomachus's theorem. ∎
(b) Proof that
$$ 1^3+2^3+\cdots+n^3=(1+2+\cdots+n)^2. $$
From part (a), the number $m^3$ is the sum of the $m$ consecutive odd integers
$$ m^2-m+1,\ m^2-m+3,\ \ldots,\ m^2+m-1. $$
Observe that the last odd integer in the block for $m^3$ is
$$ m^2+m-1, $$
while the first odd integer in the block for $(m+1)^3$ is
$$ (m+1)^2-(m+1)+1 = m^2+m+1. $$
Since
$$ (m^2+m-1)+2=m^2+m+1, $$
the block for $(m+1)^3$ begins exactly with the next odd integer after the block for $m^3$.
Therefore, when the blocks for
$$ 1^3,,2^3,,\ldots,,n^3 $$
are concatenated, they form the sequence of the first
$$ 1+2+\cdots+n $$
odd integers:
$$ 1,3,5,\ldots,2!\left(1+2+\cdots+n\right)-1. $$
Hence
$$ 1^3+2^3+\cdots+n^3 $$
is equal to the sum of the first
$$ N=1+2+\cdots+n $$
odd integers.
It remains to use the classical fact that the sum of the first $N$ odd integers is $N^2$. Indeed,
$$ \begin{aligned} 1+3+5+\cdots+(2N-1) &=\sum_{j=1}^{N}(2j-1)\ &=2\sum_{j=1}^{N}j-\sum_{j=1}^{N}1\ &=2\cdot\frac{N(N+1)}2-N\ &=N^2. \end{aligned} $$
Therefore
$$ 1^3+2^3+\cdots+n^3=N^2. $$
Substituting
$$ N=1+2+\cdots+n $$
gives
$$ \boxed{ 1^3+2^3+\cdots+n^3 = \left(1+2+\cdots+n\right)^2 }. $$
This is the desired formula. ∎