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.

For example, we know that the following is true (and can be easily derived):

$\sum\limits_{x=1}^{n}x = \frac{1}{2}n(n+1)$

But, what if we wanted to find the sum of a series like this:

$\sum\limits_{x=1}^{n}x(2x+1)$

Wolfram|Alpha tells me that the answer is $\frac{1}{6}n(n+1)(4n+5)$, but I'm at a loss as to how it came up with this answer. Is there a simple method for finding the general formula for a partial sum of the form $\sum\limits_{x=1}^{n}y(x)$ where $y(x)$ is a polynomial with rational roots?

share|improve this question
1  
There are formulas for $\sum_{k=1}^n k^d$ for any positive integer $d$. The general formula is nowadays often called Faulhaber's Formula. There is no really good reason for the name, the result is due to Bernoulli. This enables us to handle $\sum_{k=1}^n P(k)$ for any polynomial. –  André Nicolas Jun 11 '13 at 6:46
add comment

4 Answers

up vote 4 down vote accepted

Let $p(x)=\sum\limits_{i=0}^{n} a_{i}x^{i}$

Say you wan't to find $\sum p(x)$.

There is a general formula for $\sum x^{k}$.

$$1^{k}+2^{k}+\cdots+n^{k}=\sum\limits_{i=1}^{k}S(k,i)\binom{n+1}{i+1}i!\\=\frac{n^{k+1}}{k+1}+\frac{1}{2}n^{k}+B_{1}\frac{r}{2!}n^{r-1}-\cdots$$

Where $S(k,i)$ is the Stirling number of the Second Kind and $B_{r}$ denots the the Bernoulli's Numbers.

So using that you can find the sum of any polynomial.

The given sum- $$\sum x(2x+1)=2\sum x^{2}+\sum x=2\binom{n+1}{2}+4\binom{n+1}{3}+\binom{n+1}{2}=\frac{1}{6}n(n+1)(4n+5)$$

share|improve this answer
    
I can't believe that I didn't notice this; thank you. –  Undeterminant Jun 11 '13 at 6:46
add comment

Here is my favorite method which works for any polynomial (rational roots or otherwise) and you only need to remember two basic facts, one from calculus one and one about polynomials. First, since summations are analogous to integration, we have that

$$\int x^k \approx x^{k+1} \Rightarrow \sum x^k \approx x^{k+1}.$$

For your problem, let us define

$$f(n)=\sum_{x=1}^n x(2x+1)$$

and since the summand is a polynomial of degree two, the sum $f(n)$ must be a polynomial of degree three. Then using the (second) fact that a polynomial of degree three can be uniquely determined by four points, use points $$(1,f(1)),(2,f(2)),(3,f(3)),(4,f(4))$$ and compute the unique interpolating polynomial and you get

$$f(n)=\frac{1}{6}n(n+1)(4n+5).$$

Come to think of it, this should work for complex polynomials too.

Done, done, and done!

share|improve this answer
add comment

First of all, note that: $\sum\limits_{x=1}^{n}x(2x+1) = 2\sum\limits_{x=1}^n x^2 + \sum\limits_{x=1}^n x$.

$\sum\limits_{x=1}^n x^2$ are known as pyramidal number (google around for it) and they have a closed form solution:

$\sum\limits_{x=1}^n x^2 = \frac{2n^3 + 3n^2 + n}{6}$

You already know that $\sum\limits_{x=1}^n x = \frac{n^2 + n}{2}$.

Then, solution is given.

BTW, I don't know if there is a general formula for any $\sum\limits_{x=1}^n x^k$.

share|improve this answer
add comment

Hint:$$\sum\limits_{x=1}^{n}x(2x+1)=2\sum\limits_{x=1}^{n}x^2+\sum\limits_{x=1}^{n}x =2(\frac{n(n+1)(2n+1)}{6})+\frac{1}{2}n(n+1)$$

share|improve this answer
add comment

Your Answer

 
discard

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.