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:

 $\begin{array}[]{cccccccccc}&1&+&2&+&3&+&\cdots&+&n\\ +&n&+&(n-1)&+&(n-2)&+&\cdots&+&1\\ =&n+1&+&n+1&+&n+1&+&\cdots&+&n+1\\ \end{array}$

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

 $\sum_{k=1}^{n}k=\frac{n(n+1)}{2}.\qed$

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}\binom{r+1}{l}\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}+\cdots+n^{2}=\frac{n(n+1)(2n+1)}{6},$
 $1^{3}+2^{3}+3^{3}+\cdots+n^{3}=\frac{(n(n+1))^{2}}{4},$

and

 $1^{4}+2^{4}+3^{4}+\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,

 $\displaystyle f_{n}(x)$ $\displaystyle=(e^{(n+1)x}-1)\sum_{j=0}^{\infty}B_{j}\frac{x^{j}}{j!}$ $\displaystyle=\sum_{l=1}^{\infty}\sum_{j=0}^{\infty}B_{j}(n+1)^{l}\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}\binom{r+1}{l}\frac{B_{r+1-l}}{r+1}(n+1)^{% l}.\qed$

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.

Title sum of $r$th powers of the first $n$ positive integers SumOfRthPowersOfTheFirstNPositiveIntegers 2013-03-22 14:14:38 2013-03-22 14:14:38 mathcam (2727) mathcam (2727) 14 mathcam (2727) Theorem msc 11B68 msc 05A15 BernoulliNumber FormalPowerSeries ArithmeticProgression SumOfPowers