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

(more info)

Math for the people, by the people.

Main Menu

sections Encyclopædia
Papers
Books
Expositions

meta Requests (194)
Orphanage
Unclass'd
Unproven (498)
Corrections (25)
Classification

talkback Polls
Forums
Feedback
Bug Reports

downloads Snapshots
PM Book

information News
Docs
Wiki
ChangeLog
TODO List
Legalese
About

sum of

th powers of the first $n$

positive integers

(Theorem)

A very classic problem is this: what is the sum of the numbers from to ? The answer is , 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

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

Proof. Write the sum twice:

$\begin{displaymath} \begin{array}{cccccccccc} & 1 & + & 2 & + & 3 & + & \cdots &... ... n+1 & + & n+1 & + & n+1 & + & \cdots & + & n+1 \ \end{array}\end{displaymath}$

which is exactly

, so

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

$\qedsymbol$

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

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

Theorem 2 Let denote the th Bernoulli number, and let be a positive integer. Then

$\displaystyle \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

of degree

; for a given

, we can look up all the Bernoulli numbers we need and write down the polynomial explicitly. For example:

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

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

and

$\displaystyle 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

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

On the one hand, we have

$\displaystyle 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

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

Combining these two results, we get

$\displaystyle \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.\qedhere$

$\qedsymbol$

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

This proof is given as Exercise 2.23 in generatingfunctionology.

"sum of

th powers of the first $n$

positive integers" is owned by mathcam. [ full author list (2) | owner history (1) ]

(view preamble)

Attachments:: alternate form of sum of th powers of the first positive integers (Proof) by rm50

Log in to rate this entry.
(view current ratings)

Cross-references: proof, computer algebra system, coefficient, obvious, argument, generating function, polynomial, positive, Bernoulli number, integer, numbers, sum
There are 3 references to this entry.

This is version 11 of sum of $r$

th powers of the first $n$

positive integers, born on 2004-03-12, modified 2004-10-16.
Object id is 5689, canonical name is SumOfKthPowersOfTheFirstNPositiveIntegers.
Accessed 3631 times total.

Classification:

AMS MSC:	11B68 (Number theory :: Sequences and sets :: Bernoulli and Euler numbers and polynomials)
	05A15 (Combinatorics :: Enumerative combinatorics :: Exact enumeration problems, generating functions)

Pending Errata and Addenda

None.[ View all 5 ]

Discussion

forum policy

No messages.

Interact