Sums of powers II: Faulhaber and Bernoulli
Previously: Sums of powers I: with and without replacement
Last year I wrote about formulas for the sum of powers
I argued that the more natural way to think about this was instead through the falling factorial
If you want to get the powers result back, we can do so with Stirling numbers: it’s
However, I recently read a delightful exposition of a way to get the sums of powers sums directly, without going via the falling factorial, in The Book of Numbers by Conway and Guy (Chapter 4). This blogpost is basically entirely from that book.
Faulhaber polynomials
As a reminder, the formulas for the sums, written out as polynomials are
(These are sometimes called Faulhaber polynomials, after the German mathematician Johann Faulhaber who first found the rule for them in 1530 or so.) You might be able to see a pattern starting to arise here – I’ve put some of the fractions not in their simplest form, but in a form that suggests some of the emerging patterns.
Bernoulli numbers
The coefficients of the Faulhaber polynomials are related to a sequence of numbers called the Bernoulli numbers, which begin
I was vaguely aware that the Bernoulli numbers were involved somewhere here, but I’ve never really liked the Bernoulli numbers, as they were defined through some baffling formula I could never remember, whose relationship to the sums of powers was totally opaque. But the exposition of Conway and Guy (not, I don’t think, orginal to them) makes everything so much clearer.
You’ll have noticed that I wrote the sequence of Bernoulli numbers as
Let’s define the Bernoulli numbers and see our first example of this “power” notation together.
Definition. The Bernoulli numbers
What a simple and easy-to-remember equation! Let’s see what it means. The first case is the
We must first expand out the brackets on the left-hand side, to get
We can now treat this as a legitimate equation about
Now that we know
The
We can keep going like this. You might like to check that the equation
Faulhaber’s formula
Faulhaber’s formula for the sums of powers is then this:
Remember, still, that the term
Let’s just test this works with
using
If we wanted to avoid the “Bernoulli numbers as powers of
But am I going to be able remember that? I doubt it – but I can remember
All that remains is to actually prove this formula. The key is to look at a difference
The first term is
while the second term is
Now the first term in both of these,
Now we sum up all the differences. So what is
On one hand, by the above, its
But, on the other hand, a sum of differences like this will “telescope” to
Hence we have
and dividing both sides by