Possible Duplicate:
why is $\sum\limits_{k=1}^{n} k^m$ a polynomial with degree $m+1$ in $n$

I'm searching for a way to find the partial sum of a polynomial, is there any way of doing this formulaically instead of just guessing and checking?

For example...

$$\sum_{x=1}^n {x^{2}}=?$$


$$\sum_{x=1}^n (4x^2+7x+2)=?$$


marked as duplicate by t.b., Asaf Karagila, J. M. is a poor mathematician, Zev Chonoles Jan 24 '12 at 4:32

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.


Because of linearily, it is enough to find $S_k(n)=\sum_{x=0}^nx^k$.

This can be done with Bernoulli polynomials using Faulhaber's formula.

A little computation using this information shows that, for example, $$\sum_{x=1}^N(4x^2+7x+2)=\frac{1}{6} \left(8 N^3+33 N^2+37 N\right).$$


You can also find a formula directly. The partial sums of a polynomial function are given by a polynomial function. Since the higher-order differences of the values of a polynomial function are eventually zero, you can go backwards and find an expression for the sum in terms of Newton polynomials with coefficients the first element in each row of differences; see http://en.wikipedia.org/wiki/Newton_series#Newton.27s_series.

For your example, the differences are

$0 \quad 13 \quad 45 \quad 104 \quad 198$

$13 \quad 32 \quad 59 \quad 94$

$19 \quad 27 \quad 35 $

$8 \quad 8$


and so the formula is $$ 0{n \choose 0} + 13{n \choose 1}+19{n \choose 2}+8{n \choose 3} $$ which of course agrees with Mariano's answer.


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