# 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}& \hfill 1\hfill & \hfill +\hfill & \hfill 2\hfill & \hfill +\hfill & \hfill 3\hfill & \hfill +\hfill & \hfill \mathrm{\cdots}\hfill & \hfill +\hfill & \hfill n\hfill \\ \hfill +\hfill & \hfill n\hfill & \hfill +\hfill & \hfill (n-1)\hfill & \hfill +\hfill & \hfill (n-2)\hfill & \hfill +\hfill & \hfill \mathrm{\cdots}\hfill & \hfill +\hfill & \hfill 1\hfill \\ \hfill =\hfill & \hfill n+1\hfill & \hfill +\hfill & \hfill n+1\hfill & \hfill +\hfill & \hfill n+1\hfill & \hfill +\hfill & \hfill \mathrm{\cdots}\hfill & \hfill +\hfill & \hfill n+1\hfill \end{array}$$ |

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

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

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)(3{n}^{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{\u220e}$$ |

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 |