# Evaluating N-th partial sums of polynomials [duplicate]

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

How can I find $\sum_{n=1}^N n^2-n$? Wolfram Alpha will tell you that it is $\frac{N}{3} (N-1)(N+1)$, and given the famous formulas for $\sum_{n=1}^N n^2$ and $\sum_{n=1}^N n$, you could piece together the first. But is there some sort of a general method here that might be of use in evaluating these kinds of partial sums?

## marked as duplicate by Hans Lundmark, William, Did, J. M. is a poor mathematician, NorbertOct 3 '12 at 20:08

• ... just to mention one of many duplicates. – Hans Lundmark Sep 4 '12 at 15:08
• Here is a general method. – Mhenni Benghorbal Sep 4 '12 at 16:12
• @Mhenni You did it again! Please stop linking to your own answers when they are not of any help. This is despicable self-promotion. – Did Sep 5 '12 at 20:29

I'm not sure what you mean by general but here are two ways to find $\sum_{n=1}^N p(n)$ for $p$ a polynomial.
• If $p$ has degree $d$, find the value of the sum for $d+2$ values of $N$ and use Lagrange interpolation.
• Write $p(n)$ in the binomial basis $n \choose k$ and use sum-of-column identity in the Pascal triangle.
• How do you know a priori that the sum is given by a degree $d+1$ polynomial? – user21725 Sep 4 '12 at 14:05
• ... because one easily sees that taking differences (i.e. $f\mapsto (n\mapsto f(n+1-f(n))$ of degree $d+1$ poynomials produces degree $d$ poynomials and that this is surjective. – Hagen von Eitzen Sep 4 '12 at 14:49
Yes. The formula for the sum of the first $N$ powers $n^p$ is known as Faulhabers Formula, and the proof involving the binomial theorem can also be found in the given link.
Well, if you're interested in the sums of the form $$\sum_{n=1}^N n(n+1) \cdots (n+r)$$ then there is a nice closed form, $$\sum_{n=1}^N n(n+1) \cdots (n+r) = \frac{1}{r+2} N(N+1) \cdots (N+r+1)$$ This follows from writing $$n(n+1) \cdots (n+r) = \frac{ n(n+1) \cdots (n+r)(n+r+1) - (n-1)n(n+1) \cdots (n+r)}{r+2}$$ and noting that the numerator is telescopic.