Welcome to NRICH.

 
The sums of powers of integers.
This is a merger of two discussions on the same topic.
By Anonymous on Thursday, August 31, 2000 - 04:37 pm:

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)n2(n+1)2.
The sum of the first n fourth powers is (1/30)n(n+1)(2n+1)(3n2+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?

By Stuart Scott (M840) on Wednesday, November 15, 2000 - 02:22 pm:

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)n2(n+1)2

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(ip) 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(ip) 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.n2.(n+1)2
S(4,n) = 1/30.n.(n+1).(2n+1).(3n2+3n-1)
S(5,n) = 1/12.n2.(n+1)2.(2n2+2n-1)
S(6,n) = 1/42.n.(n+1).(2n+1).(3n4+6n3-3n+1)
S(7,n) = 1/24.n2.(n+1)2.(3n4+6n3-n 2-4n+2)
S(8,n) = 1/90.n.(n+1).(2n+1).(5n6+15n5+5n4-15n 3-n2+9n-3)
S(9,n) = 1/20.n2.(n+1)2.(n2+n-1).(2n4+4n 3-n2-3n+3)
S(10,n) = 1/66.n.(n+1).(2n+1).(n2+n-1).(3n6+9n5+2n 4-11n3+3n2+10n-5)
S(11,n) = 1/24.n2.(n+1)2.(2n8+8n7+4n 6-16n5-5n4+26n3-3n2-20n+10)
and
S(12,n) = 1/2730.n.(n+1).(2n+1).x
S(13,n) = 1/420.n2.(n+1)2.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

By Andrew Smith (P2517) on Thursday, August 31, 2000 - 09:11 pm:

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/2n2 + 1/2n. Multiply by r, n2 + n. Integrate, 1/3n3 + 1/2n2 and add on the linear term (1 - 1/3 - 1/2)n to give the answer above.

The second way is to use the formula (its messy I'm afraid), sum of rth powers from 1 to n = Sr(n) = (1/(r+1))*Sr j=0[(r+1)C(j)]*Bj*(n+1)r+1-j

where [(r+1)C(j)] = (r+1)!/(j!*(r+1-j)!)

and Bj is the jth Bernoulli number where the mth Bernoulli number is Bm = -(1/(m+1))*Sm-1 j=0[(m+1)C(j)]*Bj and B0 = 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.

By Neil Morrison (P1462) on Friday, September 1, 2000 - 07:35 am:

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:

nk+1 - (n-1)k+1 = k+1C1nk - k+1C2nk-1 ... + (-1)r[k+1Cr]nk+1-r ... + (-1)k+2

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

adding all these equations:

nk+1 = [k+1C1Sn 1xk] ... + (-1)r+1[k+1Cr]Sn 1xk+1-r ... +(-1)k+1Sn 11.

rearranging and dividing by k+1 give a formula for the sum of kth powers, which has an nk+1 term, and a term in each sum of (k-r)th powers right down to the constant term.

I experimented for a while, but there doesn't seem to be any simpler way to write all this (just complicates it more, as your formula shows)
and it was late at night, so I just left it at that. However, at least if we can't get a general formula we've a reasonable way of getting a simple answer for given k.

You just have to fiddle with polynomials if you know k.

Neil M

By Michael Doré (Md285) on Wednesday, November 15, 2000 - 02:52 pm:

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 rn from 1 to x and expand out the resultant polynomial in x, the coefficient of xn+1 is 1/(n+1) while the coefficient of xn 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

By James Lingard (Jchl2) on Wednesday, November 15, 2000 - 03:01 pm:

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.