Generalizing the sum of consecutive cubes $\sum_{k=1}^n k^3 = \Big(\sum_{k=1}^n k\Big)^2$ to other odd powers We have,
$$\sum_{k=1}^n k^3 = \Big(\sum_{k=1}^n k\Big)^2$$
$$2\sum_{k=1}^n k^5 = -\Big(\sum_{k=1}^n k\Big)^2+3\Big(\sum_{k=1}^n k^2\Big)^2$$
$$2\sum_{k=1}^n k^7 = \Big(\sum_{k=1}^n k\Big)^2-3\Big(\sum_{k=1}^n k^2\Big)^2+4\Big(\sum_{k=1}^n k^3\Big)^2$$
and so on (apparently). 
Is it true that the sum of consecutive odd $m$ powers, for $m>1$, can be expressed as sums of squares of sums* in a manner similar to the above? What is the general formula? 
*(Edited re Lord Soth's and anon's comment.)
 A: Too long for a comment on @Gottfried's answer. (Note: This was written before the answer was edited to include notes about the matrix $E$.)

In matrix $D$, the main diagonal consists of $2$s, and the next consists of squares:
$$\begin{align}
D_{r,r\phantom{-1}} &= 2 & r \geq 1\\
D_{r,r-1} &= (r-1)^2 = \binom {r-1}{1}\frac{r-1}{1} & r \geq 3
\end{align}$$
The third diagonal consists of consecutive 4-dimensional pyramidal numbers (OEIS #A002415); the next, consecutive 6-dimensional square numbers (OEIS #A040977); the next, consecutive 8-dimensional square numbers (OEIS #A053347).
If I've done my index arithmetic correctly (please double-check), we have
$$\begin{align}
D_{r,r-2} &= \binom{r-1}{3}\frac{r-2}{2} & r \geq 5 \\
D_{r,r-3} &= \binom{r-1}{5}\frac{r-3}{3} & r \geq 7 \\
D_{r,r-4} &= \binom{r-1}{7}\frac{r-4}{4} & r \geq 9 
\end{align}$$
where row and column indices start at $1$. The two entries of the final visible column satisfy
$$D_{r,r-5} = \binom{r-1}{9}\frac{r-5}{5} \qquad r \geq 11$$
So, for $r\neq c$, the non-zero entries of $D$ appear to be
$$D_{r,c} = \binom{r-1}{2(r-c)-1}\frac{c}{r-c}$$
A: This is not an answer but does not fit in a comment-box. 
Another way to describe the relation between the  sums and the sums of squares of various sums-of-like-powers makes use of the Eulerian-numbers, which converts the expressions for the sums-of-like-powers into polynomials.  The sums of like powers can be expressed as
$$\small \begin{array} {rclllll}  
s_0(n) = & 1 \cdot  \binom{n}{1}  \\ 
s_1(n) = & & 1 \cdot \binom{n+1}{2} \\ 
s_2(n) = & & 1 \cdot \binom{n+1}{3}& +1 \cdot \binom{n+2}{3} \\ 
s_3(n) = & & 1 \cdot \binom{n+1}{4}& +4 \cdot \binom{n+2}{4} & +1 \cdot \binom{n+3}{4} \\
s_4(n) = & & 1 \cdot \binom{n+1}{5}& +11 \cdot \binom{n+2}{5} & +11 \cdot \binom{n+3}{5} & +1 \cdot \binom{n+4}{5} \\ 
s_5(n) = & & 1 \cdot \binom{n+1}{6}& +26 \cdot \binom{n+2}{6}& +66 \cdot \binom{n+3}{6} & +26 \cdot \binom{n+4}{6} & +1 \cdot \binom{n+5}{6} \\ 
 \vdots &  &\vdots
 \end{array}
$$
This looks a bit more regular than the expressions by Bernoulli-polynomials and possibly the relations between the sums-expressions of odd orders $s_{2k+1}(n)$ can be written using these polynomials nicely and with  more ease than with the Bernoulli-polynomials, don't know.      
The first of your equality would then be expressed as
$$ \begin{array} {rcl} \sum_{k=1}^n k^3 &=&\left(\sum_{k=1}^n k \right)^2 \\  s_3(n) &=& s_1(n)^2 \\
 1 \cdot \binom{n+1}{4} +4 \cdot \binom{n+2}{4}  +1 \cdot \binom{n+3}{4} &=& \left( 1 \cdot \binom{n+1}{2}\right)^2 \\
 \end{array}$$ 
and which must then be expanded to reproduce the equality (but I've not the time at the moment to do this in the required length...)
A: This is a partial answer, it just establishes the existence.
We have
$$s_m(n) = \sum_{k=1}^n k^m = \frac{1}{m+1}
\left(\operatorname{B}_{m+1}(n+1)-\operatorname{B}_{m+1}(1)\right)$$
where $\operatorname{B}_m(x)$ denotes the monic
Bernoulli polynomial
of degree $m$, which has the following useful properties:
$$\begin{align}
\int_x^{x+1}\operatorname{B}_m(t)\,\mathrm{d}t &= x^m
 \quad\text{(from which everything else follows)}
\\\operatorname{B}_{m+1}'(x) &= (m+1)\operatorname{B}_m(x)
\\\operatorname{B}_m\left(x+\frac{1}{2}\right) &\begin{cases}
 \text{is even in $x$} & \text{for even $m$}
\\ \text{is odd in $x$}  & \text{for odd $m$}
\end{cases}
\\\operatorname{B}_m(0) = \operatorname{B}_m(1) &= 0
\quad\text{for odd $m\geq3$}
\end{align}$$
Therefore,
$$\begin{align}
s_m(n) &\text{has degree $m+1$ in $n$}
\\s_m(0) &= 0
\\s_m'(0) &= \operatorname{B}_m(1) = 0\quad\text{for odd $m\geq3$}
\\&\quad\text{(This makes $n=0$ a double zero of $s_m(n)$ for odd $m\geq3$)}
\\s_m\left(x-\frac{1}{2}\right) &\begin{cases}
 \text{is even in $x$} & \text{for odd $m$}
\\ \text{is odd in $x$}  & \text{for even $m\geq2$}
\end{cases}
\end{align}$$
Consider the vector space $V_m$ of univariate polynomials $\in\mathbb{Q}[x]$
with degree not exceeding $2m+2$, that are even in $x$ and have a double zero
at $x=\frac{1}{2}$.
Thus $V_m$ has dimension $m$ and is clearly spanned by
$$\left\{s_j^2\left(x-\frac{1}{2}\right)\mid j=1,\ldots,m\right\}$$
For $m>0$, we find that $s_{2m+1}(x-\frac{1}{2})$ has all the properties
required for membership in $V_m$.
Substituting $x-\frac{1}{2}=n$, we conclude that there exists a representation
$$s_{2m+1}(n) = \sum_{j=1}^m a_{m,j}\,s_j^2(n)
\quad\text{for $m>0$ with $a_{m,j}\in\mathbb{Q}$}$$
of $s_{2m+1}(n)$ as a linear combination of squares of sums.
A: Power Sums of Binomial Coefficients
