# 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?

-

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

-
Thanks a lot. I enjoyed reading D. Knuth's paper. –  Denis Serre Jun 8 '11 at 9:54

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.

-

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.

-
Hmmm surely we can all only guess what it was that the OP had in mind, but your answer seems to be oversimplifying the question a bit. It's as though someone asked you how to compute the derivative of $x^x$, and you told them that there is that nice way of computing the derivative of $x^n$ using the binomial formula... :-) –  Vladimir Dotsenko Jun 7 '11 at 18:05
I suppose you're right, but that is my answer: he's asking the wrong question! To my eye, expressions like $\sum n^3$ are ugly and unnatural, and any nice expressions (like the one OP gives) that happen must be either coincidence or the result of some binomial coefficient identity arising from conversion between $\sum n^3$ and $\sum n^{\underline 3}$. –  Kevin O'Bryant Jun 7 '11 at 18:47

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).

-
oops, thanks @Allen :) –  Ale De Luca Jun 7 '11 at 12:22
$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$
$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.