The following three formulae are reasonably well known:
1 + 2 + 3 + ... + n = n(n+1)/2
1
2 + 2
2 + 3
2 + ... + n
2 = n(n+1)(2n+1)/6
1
3 + 2
3 + 3
3 + ... + 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:
1
4 + 2
4 + 3
4 + ... + n
4 = n(n+1)(2n+1)(3n
2+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, s
n, is the sum 1
5 + 2
5 + ... + n
5 -- 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, 3
1 111, 2
2 3
1 231, 2
2 5
2 13
1, 3
1 5
2 591, 3
1 7
2 831, 2
4 7
2 37
1, 2
4 3
3 111 131, 3
3 5
2 1791, 5
2 11
2 73
1and 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 2n
2 + 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), s
n is divisible by 2n
2 + 2n - 1. You can check that for n = 1, 2, ..., 10, the term s
n is always divisible by (2n
2 + 2n - 1)/3. So now consider the sequence t
n = s
n / ((2n
2 + 2n - 1)/3). The numbers t
1 through t
10 are
1, 9, 36, 100, 225, 441, 784, 1296, 2025, 3025
and I recognized that all of these are squares; in particular t
n = (n(n+1)/2)
2.
Putting everything together, I get the conjecture that the sum of the first n fifth powers
s
n = n
2(n+1)
2(2n
2+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.