The Unapologetic Mathematician

Faulhaber’s Fabulous Formula

Tonight I’ll be telling the undergrad math club here about a nifty little thing I picked up from Scott Carter last week, who in turn picked it up from John Conway shortly before that: Faulhaber’s Fabulous Formula. The formula itself expresses the sum of the first $n$ $p$-th powers as (sort of) an integral:

$\displaystyle\sum\limits_{k=1}^nk^p=\int\limits_b^{b+n}x^p\,dx$

The question here is what this mysterious $b$ is, and the answer to that takes us into the shadowy netherworld of 19th-century analysis: the umbral calculus.

Our mysterious character $b$ is defined by a simple equation: $b^n=(b-1)^n$. For $n=0$ this is trivially true, as both sides are $1$. For $n=1$ this is clearly nonsense, as it says $b^1=b^1-1$, or $0=-1$, so let’s just not apply the relation for this value of $n$. For higher $n$, it’s still nonsense, but of a subtler sort. So let’s dive in.

When we consider $n=2$ we get $b^2=b^2-2b^1+1$. The $b^2$ terms cancel, and what’s left tells us that $b^1=\frac{1}{2}$. So $b=\frac{1}{2}$? Not quite, because that would make sense!

Let’s look at $n=3$. Now the relation reads $b^3=b^3-3b^2+3b^1-1$. Again the $b^3$ terms cancel, and now we know that $b^1=\frac{1}{2}$. Thus we can solve to find $b^2=1/6$. Huh?

Moving on to $n=4$, we find $b^4=b^4-4b^3+6b^2-4b^1+1$. The $b^4$ terms cancel and we substitute in the values we know for $b^2$ and $b^1$ to find $b^3=0$. As I told Scott, “you do realize that this is f___ing nuts, right?”

We can keep going on like this, spinning out values of $b^n$ for all $n\geq1$$b^4=-\frac{1}{30}$, $b^5=0$, $b^6=\frac{1}{42}$, $b^7=0$, $b^8=-\frac{1}{30}$, $b^9=0$ — which have absolutely nothing to do with powers of any base $b$. But we use them as powers in the relation. Remember: this is prima facie nonsense.

But onwards, mathematical soldiers, integrating as to war: we take the integral and break it up into $n$ pieces:

$\displaystyle\int\limits_b^{b+n}x^p\,dx=\sum\limits_{k=1}^n\int\limits_{b+k-1}^{b+k}x^p\,dx$

Even (most of) my calculus students can take the antiderivatives on the right to get

$\displaystyle\frac{x^{p+1}}{p+1}\Biggl\vert_{b-1+k}^{b+k}=\frac{(b+k)^{p+1}-((b-1)+k)^{p+1}}{p+1}$

Now we use the binomial formula to expand each of the terms in the numerator.

$\displaystyle\frac{1}{p+1}\left(\sum\limits_{l=0}^{p+1}\binom{p+1}{l}b^lk^{p+1-l}-\sum\limits_{l=0}^{p+1}\binom{p+1}{l}(b-1)^lk^{p+1-l}\right)$

and combine to find

$\displaystyle\frac{1}{p+1}\sum\limits_{l=0}^{p+1}\binom{p+1}{l}k^{p+1-l}\left(b^l-(b-1)^l\right)$

But we said that $b^n=(b-1)^n$ unless $n=1$! That is, all these terms cancel except for one, which is just $k^p$. And so the integral we started with is the sum of the first $n$ $p$-th powers, as we wanted to show.

So how do we apply this? Well, we can evaluate the integral more directly rather than breaking it into a big sum.

$\displaystyle\int_b^{b+n}x^p\,dx=\frac{(b+n)^{p+1}-b^{p+1}}{p+1}=\sum\limits_{l=0}^{p}\binom{p+1}{l}\frac{n^{p+1-l}}{p+1}b^l$

And now we use the values we cranked out before. Let’s write it out for $p=1$, which many of you already know the answer for.

$\displaystyle\binom{2}{0}\frac{n^2}{2}b^0+\binom{2}{1}\frac{n}{2}b^1=\frac{n^2}{2}+\frac{n}{2}=\frac{n(n+1)}{2}$

What about $p=2$? It’s not as well-known, but some of you might recognize it when we write it out.

$\displaystyle\binom{3}{0}\frac{n^3}{3}b^0+\binom{3}{1}\frac{n^2}{3}b^1+\binom{3}{2}\frac{n}{3}b^2=\frac{n^3}{3}+\frac{n^2}{2}+\frac{n}{6}=\frac{n(n+1)(2n+1)}{6}$

In fact, given the numbers we cranked out back at the start of the post, we can use this formula to easily write out the sum of the first $n$ 9th powers:

$\displaystyle\frac{n^2(n+1)^2(n^2+n-1)(2n^4+4n^3-n^2-3n+3)}{20}$

all thanks to Faulhaber’s Fabulous Formula.

November 14, 2007 - Posted by | Uncategorized

1. Faulhaber’s formula is also discussed in Conway and Guy’s The Book of Numbers (p. 107 ff.).

I guess it’s well known, but what the hey: umbral calculus was made respectable by Gian-Carlo Rota and others. Some more information can be found here.

Comment by Todd Trimble | November 14, 2007 | Reply

2. Yes, I found those references while we were trying to figure out what Conway meant when he told Carter about this. I’m not sure if “well-known” really applies. It used to be a lot better-known, sure, but nowadays it seems to occupy a certain backwater.

Of course, these $b^n$ are “secretly” the Bernoulli numbers (with a slight tweak), and their definition mirrors the relationship between Bernoulli numbers and the binomial coefficients. Naturally (well, natural for me) the question is what the Bernoulli numbers mean combinatorially. That is, how should we categorify the umbral calculus? Is there a nice structure type that’s hiding in the shadows here?

Comment by John Armstrong | November 14, 2007 | Reply

3. How should we categorify the umbral calculus? Is there a nice structure type that’s hiding in the shadows here?

Great question, John — I was wondering the same thing. I’ll bet we’re not the first.

It just occurred to me that the proof that e and pi are transcendental given in Hardy and Wright’s An Introduction to the Theory of Numbers partakes of a certain “umbral spirit” as well (as I guess a lot of finite difference calculus does in the first place). Probably then this stuff used to be much better known.

Comment by Todd Trimble | November 14, 2007 | Reply

4. nice post this time – the topology stuff was getting a bit thick … albeit still interesting.

keep up the good work.

don

Comment by d palahnuk | November 14, 2007 | Reply

5. The case you refer to as p = 3 is actually p = 2, right?

The actual p = 3 case is nice, too; it turns out that

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

and there’s a “proof without words” of this, in which a square with sides 1 + 2 + … + n is dissected into one square with side 1, two squares of side 2, …, n squares of side n. (Or something like that; trying to dissect a square of side 3 into two squares of side 2 and a square of side 1 proves that you can’t actually do what I just said!)

Comment by Isabel | November 15, 2007 | Reply

6. Ah, that’s right. Thanks for the catch, Isabel.

You’re right about expanding the sum of the first $n$ cubes as a polynomial in the sum of the first $n$ numbers. In fact, all of the above sums can be expanded as polynomials in $\frac{n(n+1)}{2}$, and the polynomials we get are called the “Faulhaber polynomials”.

Comment by John Armstrong | November 15, 2007 | Reply

7. John,

that’s not quite true; the sum of the first n squares can’t be expanded as a polynomial in terms of the first n numbers, for the obvious reason that those are polynomials of degree 3 and 2, respectively.

I think what you meant is that any such sum is a polynomial in $n(n+1)/2$ when $p$ is odd.

One might hope that the sum of $p$th powers (which is a polynomial of degree p+1) is a polynomial in the sum of $k$th powers (which is itself a polynomial of degree k+1) whenever k+1 divides p+1; unfortunately this is not true. (Let k=2, p=5.)

Comment by Isabel | November 15, 2007 | Reply

8. Of course. It’s been a long day.

By the way, I tweaked your comment, adding “latex” to the opening “\$” characters.

Comment by John Armstrong | November 15, 2007 | Reply

9. Todd, I was just recently picking up where I last left off in John Baez’ QG lecture notes. It seems he discusses the Bernoulli numbers (and their categorification) in the homework for week 6 of Winter 2004, and there’s a particularly thorough coverage in Jeff Morton’s solution set to them.

Comment by John Armstrong | November 16, 2007 | Reply

10. […] Armstrong (definitely not a Fields medalist) provides us a discussion of Faulhaber’s Famous Formula. Those of you who who haven’t encountered its fame, might learn a little […]

Pingback by Carnival of Mathematics #21: Bar-hopping at last « Secret Blogging Seminar | December 6, 2007 | Reply