sum of rth 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 k=1nk?

Theorem 1.
k=1nk=n(n+1)2
Proof.

Write the sum twice:

1+2+3++n+n+(n-1)+(n-2)++1=n+1+n+1+n+1++n+1

which is exactly n(n+1), so

k=1nk=n(n+1)2.

Having seen this, it is natural to generalize this question further, and ask: What is k=1nkr, 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 Bm denote the mth Bernoulli numberDlmfDlmfMathworldPlanetmathPlanetmath, and let r be a positive integer. Then

k=0nkr=l=1r+1(r+1l)Br+1-lr+1(n+1)l.

Observe that this formula is a polynomialPlanetmathPlanetmath 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:

12+22+32++n2=n(n+1)(2n+1)6,
13+23+33++n3=(n(n+1))24,

and

14+24+34++n4=n(2n+1)(n+1)(3n2+3n-1)30.

We will prove the result by a generating function argument.

Proof.

For no obvious reason, let

fn(x):=x(e(n+1)x-1)(ex-1).

On the one hand, we have

fn(x)=x1-(ex)n+11-ex=xk=0nekx,

and so the coefficient of xr+1 is k=0nkr/r!, more or less the sum we want.

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

fn(x) =(e(n+1)x-1)j=0Bjxjj!
=l=1j=0Bj(n+1)lxl+jl!j!

so the coefficient of xr+1 is

l=1r+1(n+1)ll!Br+1-l(r+1-l)!.

Combining these two results, we get

k=0nkr=l=1r+1(r+1l)Br+1-lr+1(n+1)l.

Observe that we need not use the Bernoulli numbers directly; any way we can extract the Taylor coefficients of fn will give us the same results. In practical terms, we can hand fn 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 rth 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