Relations between sums of powers This question is so naive that it could have been asked before on this site. If so, I'll delete it.
Among beautiful formula, I like a lot this one:
$$\left(\sum_{n=1}^Nn\right)^2=\sum_{n=1}^Nn^3.$$
Is there any other algebraic relation between the polynomials $P_k$ defined by
$$P_k(N):=\sum_{n=1}^Nn^k \qquad?$$
I suspect yes, because $1,P_0,P_1,\ldots$ is a basis of ${\mathbb Q}[X]$ (but not a basis of the $\mathbb Z$-module ${\mathbb Z}[X]$), and if one replace $P_{\ell m}$ by $P_\ell P_m$, we get another basis. But are there nice relations?
 A: A good reference is http://mathdl.maa.org/images/upload_library/22/2975368.pdf.bannered.pdf.
A: The right way to think of this sort of thing is through the falling factorial. Set
$$ n^{\underline k} = n(n-1)(n-2)\cdots(n-k+1).$$
Then
$$ \sum_{n=1}^{N-1} n^{\underline k} = \frac{1}{k+1} N^{\underline{k+1}}$$
and
$$ \Delta n^{\underline k} = (n+1)^{\underline k} - n^{\underline k} = k n ^{\underline{k-1}}$$
for reasonable $k,N$. Knowing calculus, these are the ultimate nice formulas.
A: I'm not totally sure this fully answers your questions, but such relations are known for odd values of $k$:
$$P_{2h+1}=\frac{1}{2^{2h+2}(2h+2)} \sum_{q=0}^h \binom{2h+2}{2q}
(2-2^{2q})~ B_{2q} ~\left[(8P_1+1)^{h+1-q}-1\right]$$
where the $B_{2q}$'s are Bernoulli numbers (see Faulhaber's formula on Wikipedia).
A: http://en.wikipedia.org/wiki/Faulhaber%27s_formula
QUOTE:
Faulhaber observed that if $p$ is odd, then
$$1^p + 2^p + 3^p + \cdots + n^p$$
is a polynomial function of
$$a=1+2+3+\cdots+n= \frac{n(n+1)}{2}.$$
END OF QUOTE
QUOTE:
Donald E. Knuth (1993). "Johann Faulhaber and sums of powers". Math. Comp. (American Mathematical Society) 61 (203): 277–294. arXiv:math.CA/9207222. doi:10.2307/2152953. JSTOR 2152953.  The arxiv.org paper has a misprint in the formula for the sum of 11th powers, which was corrected in the printed version.
END OF QUOTE
CORRECT VERSION:
http://www-cs-faculty.stanford.edu/~knuth/papers/jfsp.tex.gz
A: Surely there are many: these are all polynomials in one variable, so every two of them are algebraically dependent because of the transcendence degree argument :-)
However, I am sure that this is not what you wanted to hear, so here you are a nice argument showing how to guess your formula and obtain other formulas somewhat similar to it. Note that there is a remarkable symmetry property $P_k(-1-N)=(-1)^{k+1} P_k(N)$ for $k>0$. (Basically, for $k>0$ the polynomial $P_k(x)$ is the only polynomial of degree $k+1$ solving the functional equation $f(x)-f(x-1)=x^k$ together with the condition $f(0)=0$, and then you can show that $Q_k(x)=(-1)^{k+1} P_k(-1-x)$ satisfied exactly the same conditions, which proves the symmetry property without any annoying computations.) If we re-define $P_0(N)=N+\frac12$ (and assume $P_{-1}=1$),  this symmetry will hold in general.
Now, the polynomial $P_1^2$, as a polynomial of degree $4$, should be a rational combination of $P_0$, $P_1$, $P_2$ and $P_3$ (and such a combination is clearly unique - you yourself observed that they form a basis), and because of the type of symmetry it possesses, it is actually a combination of $P_1$ and $P_3$ (because other polynomials change sign under the symmetry $N\mapsto -1-N$, and this would contradict the linear independence), and looking at it carefully we observe that the $P_1$-coefficient is equal to zero, and the $P_3$-coefficient is equal to~$1$, which is your formula. 
For the same reason, the product $P_mP_n$ is expressed as a linear combination of $P_l$ where $l\le m+n+1$, $l\equiv m+n+1\pmod{2}$, - half of the terms disappear for free! (And, because of vanishing at~$0$, the redefined $P_0=N+\frac12$ and $P_{-1}=1$ will not show up in such a combination if $m+n>0$.) 
Some examples: $6P_1P_2=5P_4+P_2$, $3P_2^2=2P_5+P_3$, $12P_2P_3=7P_6+5P_4$, $2P_3^2=P_7+P_5$, $60P_3P_4=27P_8+35P_6-2P_4$ (this last one is a bit disappointing!) etc.
A: You can also do the following
$P_k(N+1) = P_k(N)+(N+1)^k = \sum_{n=1}^{N+1} n^k = \sum_{n=1}^{N+1} ((n-1)+1)^k$
After expanding you get
$P_k(N) = 1 - (N+1)^k + \sum_{t=0}^{k}\binom{k}{t} P_t(N)$
Which I think should classify as a relation between the $P_i$'s, even if it is too simple.
