Where do summation formulas come from?

Question

It's a classic problem in an introductory proof course to prove that $\sum_{ i \mathop =1}^ni = \frac{n(n+1)}{2}$ by induction. The problem with induction is that you can't prove what the sum is unless you already have an idea of what it should be. I would like to know what the process is for getting the idea.

Wikipedia has plenty of summation formulas listed, and there are surely lots more, but I think I should be able to simplify summations without referring to a table. I don't suppose there's a universal technique for deriving all of them, but it would be good to know at least a few things to try.

This question was motivated by an answer involving summation, and while I have no doubt that it's true, I wouldn't know how to get the answer to the particular summation without being told beforehand.

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

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

Answer 3

May be with an example it might be more clear. Take for example $$1+2+...+50$$

As you can remark, you have that $$51=1+50=2+49=3+48=4+47=...$$ and thus, in $$1+...+n,$$ if $n$ is even, you sum $$\underbrace{(n+1)+...+(n+1)}_{\frac{n}{2}\ times}=\frac{n(n+1)}{2}.$$

If $n$ is odd, you sum $$\underbrace{(n+1)+...+(n+1)}_{\frac{(n-1)}{2}\ times}+\frac{n+1}{2}=\frac{(n+1)(n-1)+n+1}{2}=\frac{(n+1)(n-1+1)}{2}=\frac{n(n+1)}{2}$$

Answer 4

Like Gauß did:

Write first n numbers in ordered direction in first row. Write same numbers in opposite direction in second row. Then add column-numbers. You get $n$ times the number $n+1$. This product $n \cdot (n + 1)$ is two times the sum of first $n$ numbers. Divide by two, and you get the sum of the first $n$ numbers.

$$\begin{array}{l} \begin{array}{*{20}{c}} 1&2&.&.&.&.&.&.&{n - 1}&n\\ n&{n - 1}&.&.&.&.&.&.&2&1\\ {n + 1}&{n + 1}&.&.&.&.&.&.&{n + 1}&{n + 1} \end{array}\\ \sum\limits_{k = 1}^n k = \frac{n}{2}(n + 1) \end{array}$$