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?
$\endgroup$ 14 Answers
$\begingroup$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)$$
$\endgroup$ 1 $\begingroup$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!
$\endgroup$ $\begingroup$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$.
$\endgroup$ $\begingroup$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)$$
$\endgroup$
