# Proof that $n^k$ is equal to the sum of $n$ odd numbers?

This problem is too hard for me and I can't even find a solution online. Could someone show me at least how to start the proof ?.

Question: $n^k$ is equal to the sum of $n$ odd numbers $\left(~\mbox{for}\ k\ \mbox{greater than}\ 2\ \mbox{and}\ n\ \mbox{greater than}\ 1~\right)$.

• $k=2$ isn't it? – N.S.JOHN Oct 11 '16 at 7:22
• It seems that $k\geq 2$. So the case $k=2$ is only a part of the problem, – Robert Z Oct 11 '16 at 7:59

Let $n\geq 1$. We consider two cases.

i) If $n$ is odd then $n^{k-1}$ is odd for $k\geq 2$ and $$n^k=n\cdot n^{k-1},$$ that is $n^k$ is $n$ times the odd number $n^{k-1}$.

ii) If $n$ is even then $n\geq 2$ and $(n^{k}-(n-1))$ is a positive odd number. Hence $$n^k=(n^{k}-(n-1))+(n-1)\cdot 1,$$ that is $n^k$ is the sum of the odd number $(n^{k}-(n-1))$ and $(n-1)$ times the odd number $1$.

• @Matteo Del Seppia You asked for $k\geq 2$ and you accepted the answer which solves only the case for $k=2$. What is going on here? – Robert Z Oct 11 '16 at 7:57
• I just realized that I answered a completely different quesiton. You are most definitely right. – b00n heT Oct 11 '16 at 8:01
• @b00nheT: You answered a part of the question. An infinitely small part, admittedly ;) – String Oct 11 '16 at 8:02

You could write \begin{align} n^k&=\underbrace{n^{k-1}+n^{k-1}+...+n^{k-1}}_{n\text{ times}}\\ &\quad\\ &=\sum_{i=1}^n(n^{k-1}+s_i) \end{align} where $\{s_i\}_{i=1}^n$ is any sequence of numbers such that each $s_i$ has the opposite parity of $n^{k-1}$ and $\sum_{i=1}^n s_i=0$.

One obvious choice would be $s_i=n+1-2i$ which would render the $n$ odd numbers summing up to $n^k$ distinct.

Hints: (Assuming $k=2$) there are two possible approaches for this:

1. Induction:

$$1=1^2\ \land\ \big(1 + 3+\dots +(2n-1)\big)+2n+1=\big(n^2\big)+2n+1=(n+1)^2$$

2. The sum of the first $n$ odd numbers is: $$1 + 3+\dots +(2n-1)=\sum_{k=1}^n(2k-1)=2\sum_{k=1}^nk-n.$$ Now use the formula for the summation of the first $n$ natural numbers, which is $$\sum_{k=1}^nk=\frac{n(n+1)}2.$$

EDIT: I though the OP was asking to show that $n^2$ is the sum of the first $n$ odd numbers, which is clearly not what the original question actually is. So my answer is indeed only a very partial answer. For a complete answer see below.

• You can see the solution for the induction by going with your mouse over the yellow region – b00n heT Oct 11 '16 at 7:31
• Thanks! That was incredibly brief! – user374206 Oct 11 '16 at 7:50
• See my edit and the other answers. I'm sorry for the confusion – b00n heT Oct 11 '16 at 8:08


$\ds{n \geq 2\,,\qquad k \geq 3}$.

$$\bbox[#ffd,8px,border:1px groove navy]{\mbox{This approach shows a systematic decomposition of}\ n^{k}\ \mbox{as a sum of}\ n\ \underline{odd}\ \mbox{integers}}$$ \begin{align} n^{k} & = \pars{n^{k} - n} + n = n\pars{n^{k - 1} - 1} + n = n\pars{n - 1}m + n\,,\qquad m \equiv {n^{k - 1} - 1 \over n - 1} = \sum_{\ell = 0}^{k - 2}n^{\ell} \\ & \mbox{Note that}\ m\ \mbox{is an}\ \underline{integer}. \end{align}

$$n^{k} = n\pars{n + 1}m - n\pars{2m - 1} = \sum_{j = 1}^{n}2jm - n\pars{2m - 1} = \sum_{j = 1}^{n}\bracks{2\pars{j - 1}m + 1}$$
$$\mbox{Then,}\quad \bbox[8px,border:1px groove navy]{n^{k} = \sum_{j = 1}^{n}\bracks{2\pars{j - 1}m + 1}}\,,\qquad m \equiv {n^{k - 1} - 1 \over n - 1}\ \in \mathbb{Z}.$$ The $n$-terms $\underline{odd\ number\ sequence}$ is given by: $$1\ ,\ 1 + 2m\ ,\ 1 + 4m\ ,\ \ldots\ ,\ 1 + 2(n - 1)m$$

Example: $\ds{n = 3\,,\ k = 4\,,\quad n^{k} = 3^{4} = 81}$

\begin{align} m &= {3^{4 - 1} - 1 \over 3 - 1} = 13 \\[5mm] & \implies n^{k} = 81 = \pars{2 \times 0 \times 13 + 1} + \pars{2 \times 1 \times 13 + 1} + \pars{2 \times 2 \times 13 + 1} = 1 + 27 + 53 \end{align}

Example: $\ds{n = 8\,,\ k = 5\,,\quad n^{k} = 8^{5} = 32768}$

\begin{align} m &= {8^{5 - 1} - 1 \over 8 - 1} = {4095 \over 7} = 585 \\[5mm] & \implies n^{k} = 32768 = 1 + 1171 + 2341 + 3511 + 4681 + 5851 + 7021 + 8191 \end{align}