Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question

marked as duplicate by Hans Lundmark, William, Did, J. M., userNaN Oct 3 '12 at 20:08

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.

1  
... 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
2  
@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

3 Answers 3

up vote 1 down vote accepted

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.

share|improve this answer
    
How do you know a priori that the sum is given by a degree $d+1$ polynomial? –  Eric Gregor Sep 4 '12 at 14:05
1  
... 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.

share|improve this answer

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.

share|improve this answer

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