# Every number $n^k$ can be written as a sum of $n$ distinct odd numbers

I wish to prove that for $n,k\in\mathbb{N} > 1$, we can always write $n^k$ as a sum of $n$ odd positive integers.

I have an idea of how to approach this, but my method seems to cumbersome. I am tempted to say that this sum can be achieved by peeling the $k$-dimensional cube of side length $n$, for example: $$n^2 = \sum_{i=1}^{n}2i-1$$ by taking the layers of the $n\times n$ square and $$n^3 = \sum_{i=1}^{n}3i^3 - 3i + 1$$ by taking the layers of the $n\times n\times n$ cube, but that seems overkill and it is tedious to do in the general case.

Does anyone have a more elegant proof for this statement?

-
Seems too easy. If $n$ is even, use $n-1$ $1$'s and then a single $n^k-(n-1)$, also odd. Not elegant, for sure. We would want to put additional constraints to make the problem interesting. –  André Nicolas Dec 8 '11 at 6:09
@André That totally escaped my mind. If you post that as an answer, I would be happy to accept it. Have any suggestions on what additional constraints to apply? –  EuYu Dec 8 '11 at 6:11

Edit: The first part answers the question originally posted. At the end, there is an added comment that answers the altered question, with the added feature that the numbers form an arithmetic progression.

You took care of $n$ odd. If $n$ is even, use $n-1$ copies of $1$ and a single $n^k-(n-1)$. (Since $n$ is even, $n^k-(n-1)$ is odd.)

Or else, for $k>1$, to imitate your example for $n$ odd more closely, use $n/2$ copies of $n^{k-1}+1$, and $n/2$ copies of $n^{k-1}-1$. (For $k=1$ we are stuck with using $n$ copies of $1$.)

For sure neither solution is elegant, but they work. We would want to add some constraints to make the problem interesting.

Added comment: For $n$ odd, we can use $n^{k-1}$, $n^{k-1}\pm 2$, $n^{k-1}\pm 4$, and so on up to $n^{k-1}\pm (n-1)$. So our numbers are not only distinct, they form an arithmetic progression.

For $n$ even, we can use the same idea, with $n^{k-1}\pm 1$, $n^{k-1}\pm 3$, and so on up to $n^{k-1} \pm (n-1)$. Again, our numbers are in arithmetic progression.

-
I decided to pose the additional constraint of making the numbers distinct. Nevertheless thank you for the prompt response. –  EuYu Dec 8 '11 at 6:22
Good enough for me. Thank you for the patience with this problem. –  EuYu Dec 8 '11 at 6:51

Note that the sum of the first $n$ odd positive integers is $n^2$. By adding a certain number of 2's to the largest of these, you can get any larger integer congruent to this mod 2.

-