MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
up vote 1 down vote accepted


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}.$$



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 paper has a misprint in the formula for the sum of 11th powers, which was corrected in the printed version.



share|cite|improve this answer
Thanks a lot. I enjoyed reading D. Knuth's paper. – Denis Serre Jun 8 '11 at 9:54
For those too lazy to ungzip and compile, the published version and the arXiv version . – L Spice Oct 15 '15 at 13:58

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.

share|cite|improve this answer

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.

share|cite|improve this answer
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).

share|cite|improve this answer
oops, thanks @Allen :) – Ale De Luca Jun 7 '11 at 12:22

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.