Sums of consecutive powers

There’s a well-known formula for the sum of the first n positive integers:

1 + 2 + 3 + … + n = n(n + 1) / 2

There’s also a formula for the sum of the first n squares

12 + 22 + 32 + … + n2 = n(n + 1)(2n + 1) / 6

and for the sum of the first n cubes:

13 + 23 + 33 + … + n3 = n2(n + 1)2 / 4

It’s natural to ask whether there’s a general formula for all exponents. There is, but it’s not entirely satisfying. There’s a single formula for the sum of the pth powers of the first n positive integers, but it involves mysterious coefficients known as Bernoulli numbers. So there’s a fairly simple formula for sums of powers in terms of Bernoulli numbers, but there’s no simple formula for Bernoulli numbers.

S_p(n) = \sum_{k=1}^n k^p = \frac{1}{p+1} \sum_{j=0}^p (-1)^j {p+1\choose j} B_j n^{p-j+1}

At first glance this might not seem that useful because we have a formula for a sum in terms of another sum, but note that the sums run over different ranges. The original sum runs up to n, and in application n might be very large. The sum on the right runs up to the exponent p, and in application p is usually quite small.

The first few Bernoulli numbers Bj, starting with j = 0, are 1, -1/2, 1/6, 0, -1/30, 0, …. This short list might give you some hope of finding a nice formula for the Bernoulli numbers, but they’re full of surprises. The 12th Bernoulli number, for example, is -691/2730.

So how do you define the Bernoulli numbers? These numbers come up in many contexts, and so there are many ways to define them. One way is to say that the exponential generating function of the Bernoulli numbers is z / (exp(z)- 1). In other words, Bj is j! times the coefficient of zj in the power series for z / (exp(z)- 1) centered at z = 0.

There are a couple ways to look at this definition. The first reaction is probably disappointment. “You won’t just tell me what the Bernoulli numbers are. You tell me that I have to calculate another term of this ugly power series every time I want a new Bernoulli number?!” But from a more advanced perspective, you might be grateful that the unwieldy Bernoulli numbers have such a simple exponential generating function. Often the most useful ways to study special numbers is via their generating functions.

The next post will look at what happens when we let p be negative, and when we let n go to infinity. In other words, we’ll look at the Riemann zeta function.

3 thoughts on “Sums of consecutive powers

  1. For sums, powers aren’t the most natural thing. It turns out that “falling factorials” are. Let $latex x^{\underline 0}=1, x^{\underline p}=x\cdot (x-1)\cdots (x-p+1)$, (a total of $latex p$ factors). Then $latex \sum_{k=0}^{n-1} k^{\underline p} = \frac{1}{p+1} n^{\underline p+1}$, a formula that should excite anyone who knows any calculus. If you write a simple power as a linear combination of falling factorials, those pesky Bernoulli numbers come into play.

  2. As an interesting factoid, calculating Bernoulli numbers was the first nontrivial program (and the first true algorithm) that was ever implemented on a computer.

    Most people in the business know that Ada Lovelace is considered the first computer programmer, but few know what the first program actually did. Now you know.

Leave a Reply

Your email address will not be published. Required fields are marked *