The sum of the first n integers is (1/2)n(n+1).
The sum of the first n squares is (1/6)n(n+1)(2n+1).
The sum of the first n cubes is (1/4)n² (n+1)² .
The sum of the first n fourth powers is (1/30)n(n+1)(2n+1)(3n² +3n-1).

Can anyone prove that there is or is not a generalisation of this for the sum of the first n rth powers? If so, what is it?

Here is a simple problem that has been floating at the back of my tiny mind ever since my undergraduate years as a student of maths and physics at Liverpool University in the early 60's.

We all know the formula for the sum of the first n integers = (1/2)n(n+1) - these are the so called Triangular Numbers.
Most of us also know the sum of n squared = (1/6)n(n+1)(2n+1) - The Pyramidal Numbers.
Some of us will know the sum of n cubes = (1/4)n² (n+1)²

Let us define the general function S as the sum of first n integers raised to an arbitrary integer power p :-
S(p,n) = sum(i^p ) for i=1...n

Now here is the problem: is there any general formula for S? Are there any interesting > general relationships for example a recursive relationship of the form S(p,n) =F(S(p-j),S(p-k)) where F is some function?

I have enumerated by hand the first 14 expressions for S below (after 14 things get much more painful) but any general formula seems to elude me.

I once spoke to a maths staffer from Royal Holloway College about this problem and he unconvincingly muttered something about Stirling numbers but his vagueness underlined his uncertainty!!

-------------------------------------------------
Define S(p,n) = sum(i^p ) for i=1...n

Enumeration of S for P = 0...13:

S(0,n) = n
S(1,n) = 1/2.n.(n+1)
S(2,n) = 1/6.n.(n+1).(2n+1)
S(3,n) = 1/4.n² .(n+1)²
S(4,n) = 1/30.n.(n+1).(2n+1).(3n² +3n-1)
S(5,n) = 1/12.n² .(n+1)² .(2n² +2n-1)
S(6,n) = 1/42.n.(n+1).(2n+1).(3n⁴ +6n³ -3n+1)
S(7,n) = 1/24.n² .(n+1)² .(3n⁴ +6n³ -n² -4n+2)
S(8,n) = 1/90.n.(n+1).(2n+1).(5n⁶ +15n⁵ +5n⁴ -15n³ -n² +9n-3)
S(9,n) = 1/20.n² .(n+1)² .(n² +n-1).(2n⁴ +4n³ -n² -3n+3)
S(10,n) = 1/66.n.(n+1).(2n+1).(n² +n-1).(3n⁶ +9n⁵ +2n⁴ -11n³ +3n² +10n-5)
S(11,n) = 1/24.n² .(n+1)² .(2n⁸ +8n⁷ +4n⁶ -16n⁵ -5n⁴ +26n³ -3n² -20n+10)
and
S(12,n) = 1/2730.n.(n+1).(2n+1).x
S(13,n) = 1/420.n² .(n+1)² .y

where x and y are 10th degree polynomials with
following coefficients:-
x: 105, 525, 525, -1050, -1190, 2310, 1420, -3285, -287, 2073, -691
y: 30, 150, 125, -400, -326, 1052, 367, -1786, 202, 1382, -691

There are a few ways to work this out but none of them are very nice, here are two.

You can build up to r from the identities you already have by the telescoping method or there is another way using integration, if you want the sum of rth powers then use the sum of (r-1)th powers. Express it as a polynomial, multiply it by r, integrate it and ignore the constant term and add on a linear term with coefficient such that the sum of the coefficients of the expression for rth powers is equal to 1.

As an example if r=2, take 1/2n(n+1) express it as a polynomial 1/2n² + 1/2n. Multiply by r, n² + n. Integrate, 1/3n³ + 1/2n² and add on the linear term (1 - 1/3 - 1/2)n to give the answer above.

where $[(r+1)C(j)]=(r+1)!/(j!\times (r+1-j)!)$

and $B_j$ is the $j$th Bernoulli number where the $m$th Bernoulli number is $B_m=-(1/(m+1))\times \sum _{j=0}^{m-1}[(m+1)C(j)]\times B_j$ and $B_0=1$.

I'm not sure how much help this will all have been and sorry there's no proofs, the integration bit isn't too hard to prove but I haven't tried to prove the other.

Andrew-

Yes I was looking at this last night in a similar way: you work from the starting point of the difference of two consecutive (k+1)th powers, and add up all the such differences ending in n:

n^k+1 - (n-1)^k+1 = ^k+1 C₁ n^k - ^k+1 C₂ n^k-1 ... + (-1)^r [^k+1 C_r ]n^k+1-r ... + (-1)^k+2

and do the same for (n-1)^k+1 - (n-2)^k+1 .... right down to 1^k+1 - 0^k+1

adding all these equations:

I don't know any really easy way of working it out, although there are one or two interesting patterns in the coefficients which make it a bit easier. For example, notice that if you sum rⁿ from 1 to x and expand out the resultant polynomial in x, the coefficient of xⁿ⁺¹ is 1/(n+1) while the coefficient of xⁿ is 1/2 always. Can you see any pattern for the next few coefficients? Once you've found the patterns they are not too hard to prove.

There have actually been discussions on this topic already: look at this discussion

Of course I'd be happy to expand on anything here and there is still plenty of room for a new approach, as no-one has come up with an easy formula.

Yours,

Michael

OK, a search on Google for "polynomial for the sum of the first m nth powers" (without the quotes) provided the following link (the third of its suggestions):

http://www.mathpages.com/home/kmath279.htm

which seems to have a lot of information about this problem - although the discussion Michael's just referenced seem to cover all this anyway.

James.