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