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.

Title	sum of $r$th powers of the first $n$ positive integers
Canonical name	SumOfRthPowersOfTheFirstNPositiveIntegers
Date of creation	2013-03-22 14:14:38
Last modified on	2013-03-22 14:14:38
Owner	mathcam (2727)
Last modified by	mathcam (2727)
Numerical id	14
Author	mathcam (2727)
Entry type	Theorem
Classification	msc 11B68
Classification	msc 05A15
Related topic	BernoulliNumber
Related topic	FormalPowerSeries
Related topic	ArithmeticProgression
Related topic	SumOfPowers