Representing the cube of any natural number as a sum of odd numbers

Question

I'm expanding my notes on exercises from Donald Knuth's The Art of Computer Programming, and found something rarely mentioned in the Internet, but still useful to prove Nicomachus' Theorem about the sum of cubes.

Knuth phrases this in the following way in exercise 8(a) to chapter 1.2.1:

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.

In the answers to exercises, the author gives the following formula: $(n^2-n+1)+(n^2-n+3)+...+(n^2+n-1)=n^3$

My question is, how do I get to that formula from the sample sums given in the problem? It looks kind of odd, especially because the last summand doesn't give me any idea on how it is connected with first ones. Usually one is able to see this clearly, but not here.

I tried to get to that formula by the following set of thoughts:

To get $n^3$ one must sum up $n$ odd numbers, starting from the $(n-1)$th central polygonal number, meaning that a cube of number $n$ is made by summing up odd numbers, starting from $(n-1)$th central polygonal number to $n$th triangular number.

Since odd numbers form arithmetic progression with $a_1=1, d=2$, it's possible to use the following formula of summing up $p$th to $q$th member of this progression:

$$S_{p,q}=\dfrac{a_p+a_q}2\cdot(q-p+1)$$

We can simplify $\dfrac{a_p+a_q}2$, putting $a_p=2p-1$ and $a_q=2q-1$:

$$\dfrac{a_p+a_q}2=\dfrac{(2p-1)+(2q-1)}2=\dfrac{2p+2q-2}2=p+q-1$$

Thus, the formula of summing up $p$th to $q$th member of this progression is:

$$(p+q-1)(q-p+1)=(q+(p-1))(q-(p-1))=q^2-(p-1)^2$$

Substituting in $p=\dfrac{n(n-1)}{2}+1=\dfrac{n^2-n+2}{2}$, and $q=\dfrac{n(n+1)}{2}$, we get the formula:

$$\left(\dfrac{n(n+1)}{2}\right)^2-\left(\dfrac{n(n-1)}{2}+1-1\right)^2=\left(\dfrac{n(n+1)}{2}\right)^2-\left(\dfrac{n(n-1)}{2}\right)^2=\\ \dfrac{(n(n+1))^2-(n(n-1))^2}{4}=\dfrac{(n(n+1)-n(n-1))(n(n+1)+n(n-1))}{4}=\\ \dfrac{n^2(n+1-n+1)(n+1+n-1)}{4}=\dfrac{4n^3}{4}=n^3$$

This... kind of... proves the sum formula for any $n$, really. But it doesn't give out the formula in question, i.e. $(n^2-n+1)+(n^2-n+3)+...+(n^2+n-1)$.

What is the correct way to get this formula? Any hints are greatly appreciated.

Answer 1

Welcome to MSE!

What we're doing is moving out from $n^2$ in either direction by $2$s. You should have something analogous to gauss's trick for summing $1 \ldots n$ in mind, where we pair up $1$ and $n$, then we pair up $2$ and $n-1$, etc.

So for instance, let's look at $n = 5$. We get the sequence of numbers

$$5^2 - 4 \quad 5^2 - 2 \quad 5^2 \quad 5^2 + 2 \quad 5^2 + 4$$

Of course, if we pair these off from the outside, we see that we get $5$ copies of $5^2$. That is, $5^3$ in total. There's nothing special about $5$ in this example, and every odd number works similarly. We have $\lfloor \frac{n}{2} \rfloor$ entries on either side of $n^2$, moving by $2$s. It's easy to see these are all odd, and that they sum to $n \cdot n^2$ when we pair them off (leaving the one in the middle alone).

For even numbers, we do the obvious thing. For instance, if $n=6$ we get

$$ 6^2 - 5 \quad 6^2 - 3 \quad 6^2 - 1 \quad 6^2 + 1 \quad 6^2 + 3 \quad 6^2 + 5 $$

where now we again have $6$ copies of $6^2$, but now everybody has a friend. Since $6^2$ is even, moving to either side gives us odd numbers again.

---

As for how one might have come up with this formula, if we want to end up with $n^3$ and we want an arithmetic progression of length $n$, we know that the values should average to $n^2$ (do you see why?). Of course, once we have values averaging $n^2$ and we know we want an arithmetic progression, then we're forced to consider the sequence (let's assume $n$ is odd again, so there's a middle)

• $n^2$
• $n^2 - k \quad n^2 \quad n^2 + k$
• $n^2 - 2k \quad n^2 - k \quad n^2 \quad n^2 + k \quad n^2 + 2k$
• ...

where we continue until we have $n$ numbers total. The case $k=2$ is exactly your sequence of interest.

I'll leave the generalization of $k \neq 2$ with $n$ even to you as a (fun?) exercise!

---

I hope this helps ^_^

Answer 2

$\sum_{k=0}^{n-1} (n^2 -n + 1 + 2k)$ = $\sum_{k=0}^{n-1} n^2 + \sum_{k=0}^{n-1} (-n + 1 + 2k)$, but the second sum is 0 because of the symmetry relative to 0: $\sum_{k=0}^{n-1} (-n + 1 + 2k) = \sum_{2k\leq n-1} \left((-n+1+2k) + (n-1-2k)\right) =\sum 0$. What remains is $\sum_{k=0}^{n-1} n^2 = n\cdot n^2 = n^3$

Answer 3

I've approached the problem wrongly, as it turned out. Below is the concise solution I came up with and haven't seen elsewhere.

Let's start out from analyzing initial data:

• To get $1^3$, add $1$ odd number, starting from the $1$st odd number.
• To get $2^3$, add $2$ odd numbers, starting from the $2$nd odd number.
• To get $3^3$, add $3$ odd numbers, starting from the $4$th odd number.
• To get $4^3$, add $4$ odd numbers, starting from the $7$th odd number.

That leads to the following conclusions:

• To get $1^3$, it's needed to sum $1$st to $1$st odd numbers.
• To get $2^3$, it's needed to sum $2$nd to $3$rd odd numbers.
• To get $3^3$, it's needed to sum $4$th to $6$th odd numbers.
• To get $4^3$, it's needed to sum $7$th to $10$th odd numbers.

Hence it's needed to demonstrate that a cube of any natural number $n$ is equal to sum of $n$ odd numbers, starting from the next odd number after the last one used to get a cube of $(n-1)$.

To avoid 'notice that <...>' kind of wording with the goal of avoiding the risk of misunderstanding the way things are, it's necessary to base further logic directly on facts stated above.

If for getting, for example, the value of $2^3$ it's necessary to add $2$nd to $3$rd odd number, then it's necessary to subtract the sum of the first one odd number (technically, it's just the first odd number) from the sum of the first three odd numbers. In mathematical terms, $2^3=(1+3+5)-(1)$.

This same principle can be applied further, which can be seen below:

• $3^3=(1+3+5+7+9+11)-(1+3+5)$
• $4^3=(1+3+5+7+9+11+13+15+17+19)-(1+3+5+7+9+11)$

For purposes of clarity and concision, the first such sum be denoted as minuend sum, and the second such sum as the subtrahend sum. For example, $3^3$ has the minuend sum $1+3+5+7+9+11$ and the subtrahend sum $1+3+5$.

To be able to generalize these cases, it's necessary to have the formula of the quantity of terms in each of these two sums for any natural $n$.

According to the pattern discovered directly from the initial data, incrementing $n$ adds $n$ new terms to the minuend sum. For example, the minuend sum of $2^3$ has $2$ more terms than the minuend sum of $1^3$. Hence the minuend sum of $n^3$ will have $1+2+...+n$ terms, and the subtrahend sum will have as much terms as the minuend sum of $(n-1)^3$, i.e. $1+2+...+(n-1)$ terms.

The sequence A005408 from OEIS gives the formula for $n$th odd number: $(2n-1)$. The sum of first $n$ natural numbers has a special name in mathematics: triangular numbers. The sequence A000217 provides a formula $1+2+...+n=\dfrac{n(n+1)}2$, provable by numerous ways, one being mentioned in this question.

From here, we get:

$1+2+...+n=\dfrac{n(n+1)}2$,

$1+2+...+(n-1)=\dfrac{(n-1)((n-1)+1)}2=\dfrac{n(n-1)}2$.

Plugging these into the formula of $n$th odd number, we get the last term of the minuend sum:

$2\cdot\dfrac{n(n+1)}2-1=n(n+1)-1=n^2+n-1$

Same approach is used to get the last term of the subtrahend sum:

$2\cdot\dfrac{n(n-1)}2-1=n(n-1)-1=n^2-n-1$

Thus, this is how we generalize the initial case:

$n^3=(1+3+...+(n^2+n-1))-(1+3+...+(n^2-n-1))$

After subtracting the subtrahend sum from the minuend sum, all terms up to $(n^2-n-1)$ inclusive will cancel out, so we are left with the sum of the odd numbers from the one next to $(n^2-n-1)$, which is $(n^2-n-1+2)=(n^2-n+1)$ to $(n^2+n-1)$. Thus, we have just discovered the formula in question!

$n^3=(n^2+n+1)+(n^2+n-2)+...+(n^2+n-1)$.

Hope this will be helpful to those struggling to understand this task.