What's the nicest proof of the formula for the sum of the $k$-th powers of the first natural numbers? Do you know of a text where I can find a nicely motivated proof of the formula for $1^{k}+2^{k}+\cdots+n^{k}$?
At the very beginning of page 68 of Professor H. S. Wilf's generatingfunctionology, one can find a pretty straightforward way to obtain it but, unfortunately, there aren't any comments there regarding the "sources" of the proof.
 A: There are a few different ways to derive this formula. Perhaps the fastest is to prove that this is a polynomial of degree $k+1$ in $n,$ and use Lagrange interpolation.
Another way is to use the finite calculus. In calculus, we have $\int x^k \, dk = \frac{x^{k+1}}{k+1} + C.$
There is a formula in the finite calculus analogous to this. The finite calculus is based on the same idea as Stoke's theorem in the normal calculus: Things cancel. Particularly, if you have a complicated sum $\sum_{i=1}^n f(i)$ then maybe you can write $f(i) = F(i+1) -  F(i)$ for some different function $F.$ Then
$$\sum_{i=1}^n f(i) = \sum_{i=1}^n F(i+1) - F(i) = F(n+1) - F(1)$$
via the telescoping identity.
So, can we write $i^k = F(i+1) - F(i)$ for some function $F$, to sum our series easily?
Well, not quite. But a closely related function can be written in that form! Namely, let's try looking at what happens when we take the `finite derivative' of a polynomial. The usual integral formula says to that $x^{k+1}$ is (almost) the integral of $x^k.$ So why not guess $F(i) = i^{k+1}$ and go from there? Expanding, we get
$$F(i+1) - F(i) = (i+1)^{k+1} - i^k = \sum_{n=0}^k \binom{k+1}{n}i^n.$$
So this isn't quite $i^{k}.$ But it's close. Namely, it's some constant times $i^k,$ plus some terms involving only lower powers of $k.$ So you use intuition from usual calculus: Subtract away the antiderivatives of the lower powers, divide, and then you've found your antiderivative of $i^k$ in the finite calculus! This can be turned into a recursive algorithm to find these antiderivatives. Try finding it!
