# Where do summation formulas come from?

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.

• Generally, I imagine, they come from people figuring out a pattern for some small number of iterations and then proving it continues with induction. In particular, you might want to look up the story of Gauss as a little kid supposedly figuring out exactly the sum you wrote here in the case of $n=100$. – user137731 Mar 17 '15 at 16:04
• The book "Concrete Mathematics" by Graham, Knuth & Patashnik covers lots of techniques for computing sums. – Hans Lundmark Mar 17 '15 at 16:06
• For such sums of the form $$S_n = \sum_{k=1}^n p(k)$$ With $\deg(p) = m$, the closed form, if it exists, will be a polynomial of degree $m+1$. This and FTA will allow you to find it with a (small) finite number of evaluations ($m+2$). – AlexR Mar 17 '15 at 16:06
• Finite calculus is one way of computing sums cs.purdue.edu/homes/dgleich/publications/… – Jean-Sébastien Mar 17 '15 at 16:09
• As you surmised, there is no reason to think there is a universal method. But there are universal methods for certain families of summations. For example, there are such methods for the family of sums $\sum_1^n k^d$, where $d$ ranges over the positive integers. – André Nicolas Mar 17 '15 at 16:11

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.

• – Henry Mar 18 '15 at 8:48

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.

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

• I should have picked a harder example in my question! This sum works out nice when you add opposite ends of the sequence. What if you're summing $i^2$ instead of $i$? I don't think it's so nice then. – NoName Mar 17 '15 at 20:07

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

• This answer would be better if you explained what you were doing. – Teepeemm Mar 17 '15 at 20:51
• @Teepeemm: We are all mathematicians. We follow the rules. Thank's for advise. – Frieder Mar 17 '15 at 21:35