<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] $\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$
</s>