Partial Sum of a Polynomial

Question

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}}=?$$

or...

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

Answer 1

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

Answer 2

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$

$0$

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.