# Finding formula for partial sum of polynomial terms?

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?

-
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

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

-
I can't believe that I didn't notice this; thank you. – Undeterminant Jun 11 '13 at 6:46

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!

-

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

-

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

-