<s>[INST] Representing the cube of any natural number as a sum of odd numbers 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.
 [/INST] 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 ^_^
</s>