Where do summation formulas come from?

Solution 1:

This approach calculates $\sum_{i=1}^n i^k$ in terms of $\sum_{i=1}^n i^j$ for $j=0,1,\dots,k-1$. This lets us actually calculate $\sum_{i=1}^n i^k$ since certainly $\sum_{i=1}^n i^0 = n$. I've posted this a few times, and at this point have it saved for re-use.

We start out with this equation:

$$n^k = \sum_{i=1}^n i^k-(i-1)^k.$$

This holds for $k \geq 1$. This follows by telescoping; the $n^k$ term survives, while the $0^k$ term is zero and all the other terms cancel. Using the binomial theorem:

\begin{align*} n^k & = \sum_{i=1}^n i^k-\sum_{j=0}^k {k \choose j} (-1)^j i^{k-j} \\ & = \sum_{i=1}^n \sum_{j=1}^{k} {k \choose j} (-1)^{j+1} i^{k-j} \\ & = \sum_{j=1}^{k} {k \choose j} (-1)^{j+1} \sum_{i=1}^n i^{k-j} \end{align*}

So now we can solve this equation for $\sum_{i=1}^n i^{k-1}$:

$$\sum_{i=1}^n i^{k-1} = \frac{n^k + \sum_{j=2}^k {k \choose j} (-1)^j \sum_{i=1}^n i^{k-j}}{k}.$$

More clearly, let $S(n,k)=\sum_{i=1}^n i^k$, then

$$S(n,k)=\frac{n^{k+1} + \sum_{j=2}^{k+1} {k+1 \choose j} (-1)^j S(n,k+1-j)}{k+1}$$

for $k \geq 1$. Now start the recursion with $S(n,0)=n$.

An easy induction argument from this expression shows that $S(n,k)$ is a polynomial in $n$ of degree $k+1$. This means that if you want to get $S(n,k)$ for some large $k$, you can safely assume a polynomial form and then calculate the interpolating polynomial, rather than actually stepping up the recursion from the bottom.

Solution 2:

There do in fact exist unversal techniques for deriving exact expressions for summations. Donald Knuth asked in a problem in one of his books to develop computer programs for simplifying sums that involve binomial coefficients. The answer to that problem was given by Marko Petkovsek, Herbert Wilf and Doron Zeilberger in their book "A = B", that can de downloaded free of charge here.