sum of $r$th powers of the first $n$ positive integers

A very classic problem is this: what is the sum of the numbers from $1$ to $100$? The answer is $5050$, and there are a number of ways to see it. Before stating them, we generalize the problem somewhat: What is ${\sum }_{k=1}^{n}k$?

Theorem 1.

$$\sum _{k=1}^{n}k=\frac{n(n+1)}{2}$$

Proof.

Write the sum twice:

which is exactly $n(n+1)$, so

$$\sum _{k=1}^{n}k=\frac{n(n+1)}{2}.\mathit{∎}$$

Having seen this, it is natural to generalize this question further, and ask: What is ${\sum }_{k=1}^n{k}^r$, for any integer $r>0$?

This question, being so general, does not have such a tidy answer, but it can be solved.

Theorem 2.

Let $B_m$ denote the $m$th Bernoulli number, and let $r$ be a positive integer. Then

$$\sum _{k=0}^n{k}^r=\sum _{l=1}^{r+1}\left(\genfrac{}{}{0pt}{}{r+1}{l}\right)\frac{B_{r+1-l}}{r+1}{(n+1)}^l.$$

Observe that this formula is a polynomial in $n$ of degree (http://planetmath.org/OrderAndDegreeOfPolynomial) $r+1$; for a given $r$, we can look up all the Bernoulli numbers we need and write down the polynomial explicitly. For example:

$$1^2+2^2+3^2+\mathrm{\cdots }+n^2=\frac{n(n+1)(2n+1)}{6},$$

$$1^3+2^3+3^3+\mathrm{\cdots }+n^3=\frac{{(n(n+1))}^2}{4},$$

and

$$1^4+2^4+3^4+\mathrm{\cdots }+n^4=\frac{n(2n+1)(n+1)(3n^2+3n-1)}{30}.$$

We will prove the result by a generating function argument.

Proof.

For no obvious reason, let

$$f_n(x):=\frac{x(e^{(n+1)x}-1)}{(e^x-1)}.$$

On the one hand, we have

$$f_n(x)=x\frac{1-{(e^x)}^{n+1}}{1-e^x}=x\sum _{k=0}^n{e}^{kx},$$

and so the coefficient of $x^{r+1}$ is ${\sum }_{k=0}^n{k}^r/r!$, more or less the sum we want.

On the other hand, using the definition of the Bernoulli numbers,

$f_n(x)$$=(e^{(n+1)x}-1){\displaystyle \sum _{j=0}^{\mathrm{\infty }}}{B}_j{\displaystyle \frac{x^j}{j!}}$

$={\displaystyle \sum _{l=1}^{\mathrm{\infty }}}{\displaystyle \sum _{j=0}^{\mathrm{\infty }}}{B}_j{(n+1)}^l{\displaystyle \frac{x^{l+j}}{l!j!}}$

so the coefficient of $x^{r+1}$ is

$$\sum _{l=1}^{r+1}\frac{{(n+1)}^l}{l!}\frac{B_{r+1-l}}{(r+1-l)!}.$$

Combining these two results, we get

$$\sum _{k=0}^n{k}^r=\sum _{l=1}^{r+1}\left(\genfrac{}{}{0pt}{}{r+1}{l}\right)\frac{B_{r+1-l}}{r+1}{(n+1)}^l.\mathit{∎}$$

Observe that we need not use the Bernoulli numbers directly; any way we can extract the Taylor coefficients of $f_n$ will give us the same results. In practical terms, we can hand $f_n$ to a computer algebra system and it will print out the needed formula.

This proof is given as Exercise 2.23 in http://www.math.upenn.edu/ wilf/DownldGF.htmlgeneratingfunctionology.