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 John Armstrong | Uncategorized

10 Comments »

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
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
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
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
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
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
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
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
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
[…] 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

About this weblog

This is mainly an expository blath, with occasional high-level excursions, humorous observations, rants, and musings. The main-line exposition should be accessible to the “Generally Interested Lay Audience”, as long as you trace the links back towards the basics. Check the sidebar for specific topics (under “Categories”).

I’m in the process of tweaking some aspects of the site to make it easier to refer back to older topics, so try to make the best of it for now.

RSS Feeds

RSS - Posts
RSS - Comments
Feedback

Got something to say? Anonymous questions, comments, and suggestions at Formspring.me!
Subjects

Subjects
Archives

November 2007

M T W T F S S

1 2 3 4

5 6 7 8 9 10 11

12 13 14 15 16 17 18

19 20 21 22 23 24 25

26 27 28 29 30

« Oct Dec »
Search for:

The Unapologetic Mathematician

Mathematics for the interested outsider