04 December 2008

How could you guess the formula for the sum of the first n fifth powers?

The following three formulae are reasonably well known:

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

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

13 + 23 + 33 + ... + n 3 = (n(n+1)/2)2

(The sums of first and second powers arise pretty often naturally; the sum of cubes is rare, but it's easy to remember because the sum of the first n cubes is the square of the sum of the first n natural numbers.)

The first member of this series I can't remember is the following:

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

and generally, the sum of the first n kth powers is a polynomial of degree k+1.

I ran into these formulas, which I'd seen plenty of times before while perusing the book Gamma: Exploring Euler's Constant by Julian Havil, which I had heard of a few years ago, forgotten about, and then found while browsing the library shelves. (Also in German, under the title GAMMA: Eulers Konstante, Primzahlstrände und die Riemannsche Vermutung.) This is a most interesting book, at least if you're someone like me who pretends to know number theory but really doesn't.

Anyway, back to the main story. Say I wanted to know the sum of the first n fifth powers. Well, there's a general method for finding the formula of the first k powers; it involves the Bernoulli numbers. But let's say I didn't know that. Let's say somebody hands me the sequence

1, 33, 276, 1300, 4425, 12201, 29008, 61776, 120825, 220825

in which the nth term, sn, is the sum 15 + 25 + ... + n5 -- but doesn't tell me that's where the sequence comes from -- and challenges me to guess a formula for it in "closed form". (Smart-asses who will say that there are infinitely many formulas are hereby asked to leave.) How would I guess it?

Well, it can't hurt to find factorizations for these numbers. And if you do that you get

1, 31 111, 22 31 231, 22 52 131, 31 52 591, 31 72 831, 24 72 371, 24 33 111 131, 33 52 1791, 52 112 731

and this seems interesting; these numbers seem to have lots of small factors. Furthermore, a fair number of them seem to have one largeish prime factor, which I've bolded. (Yes, I realize, 11 times 13 isn't prime, but I actually did think of it as a large factor.) What are the large factors that I observe in these numbers? They are

?, 11, 23, ?, 59, 83, ?, 143, 179, ?

and the nth of these is easily seen to be 2n2 + 2n - 1. (Some terms don't show up from inspection of the factorizations because they get "lost in the noise", as it were.)

From there the rest is pretty easy. We see that often (but not always), sn is divisible by 2n2 + 2n - 1. You can check that for n = 1, 2, ..., 10, the term sn is always divisible by (2n2 + 2n - 1)/3. So now consider the sequence tn = sn / ((2n2 + 2n - 1)/3). The numbers t1 through t10 are

1, 9, 36, 100, 225, 441, 784, 1296, 2025, 3025

and I recognized that all of these are squares; in particular tn = (n(n+1)/2)2.

Putting everything together, I get the conjecture that the sum of the first n fifth powers

sn = n2(n+1)2(2n2+2n-1)/12

which could be proven by induction, but actually writing out the proof is best left to undergrads.

The method here is reminiscent of Enumeration of Matchings: Problems and Progress by James Propp. In that article, Propp lists various unsolved problems in the enumeration of tilings, and conjectures that some of them might have answers which are given by simple product formulas, because actually counting the tilings in question gave numbers with nice prime factorizations.

Edit, 9:13 pm: of course this is not the only method, or even the best method; it's just the method I played around with this morning. See the comments for other methods.


Unknown said...

I would have first guessed based on the pattern that it would be a 6th-degree polynomial, then computed the polynomial from the first 6 elements, then checked that it fit the rest of the sequence.

(Not this is a mathematically deep approach, but it's what I first instinct would have been if you'd asked me to figure out the sequence).

CarlBrannen said...

Or you could use the calculus of fininte differences in which case you'd get the formula and the proof that it exists for all n at the same time.

ashwin kumar b v said...

One easy way to remember the sum of k^th powers.

integral(s_k dn)+constant=s_{k+1}

Anonymous said...

Faulhaber's fantastic formula!!

In all seriousness, there are many ways to prove the existence of (or derive) the formula for the sums of powers, but the umbral calculus is amazing. I would encourage anyone who hasn't seen this approach before (which Wikipedia even describes as "shadowy") to read about it.

Michael Lugo said...

"umbral" means "shadowy".

Anonymous said...

Okay, I was trying not to self-promote too much, but A. Rex has pushed me to link to my own coverage.

Anonymous said...

Michael, I'm aware of course that "umbral" means "shad[ow]y". But I think there's a distinction between having a name and having a property, e.g. are perverse sheaves actually?

unapologetic, I meant to link to your post myself, but I couldn't remember where I had seen it. I searched for "Faulhaber's * Formula" on Google, but it didn't find it. PS. I think that, surprisingly, you're the first person to call me by the intended abbreviated form of my name.

Michael Lugo said...

A. Rex,

of course you're right, but I'm not sure that the etymology would have been obvious to everybody, and it's possible that you were just commenting that the word "shadowy" seems somehow atypical in mathematical writing.