Sums of Powers

Let Sk[N] denote the sum of the kth powers of the first N integers.  
Most people are familiar with the formulas for the first few sums 

                 S1[N] = N(N+1)/2

                 S2[N] = N(N+1)(2N+1)/6

                 S3[N] = N^2 (N+1)^2 /4

                 S4[N] = N(N+1)(2N+1)(3N^2+3N-1)/30

                           etc.

The general formula can be expressed as

                    B_(k+1)[N+1] - B_(k+1)[0]
          Sk[N]  =  --------------------------
                               k+1

where B_n[x] denotes the nth Bernoulli polynomial.  There are several 
interesting methods for deriving these formulas.  Around 1690 Jacques 
Bernoulli gave a nice description of his derivation in a short paper 
where he introduced the "Bernoulli Numbers".  He was obviously pleased
with his formulas when he wrote

 "With the help of [these formulas] it took me less than half of
  a quarter of an hour to find that the 10th powers of the first
  1000 numbers being added together will yield the sum

            91409924241424243424241924242500

  From this it will become clear how useless was the work of
  Ismael Bullialdus spent on the compliation of his voluminous
  _Arithmetica Infinitorum_ in which he did nothing more than
  compute with immense labor the sums of the first six powers,
  which is only a part of what we have accomplished in the
  space of a single page."

(One senses how distasteful Jacques found it to belittle one of his
collegues.)  Even with the formula for the sums of 10th powers, I'm 
impressed that Bernoulli could compute that number by hand in 7.5 
minutes.  Of course, using N=1000 in the base 10 probably made it 
easier.

To illustrate a typical algebraic method of determining the formula for 
Sk[N], consider the sum of the first N cubes.  By definition we have

                  S3[k+1]  =  S3[k] + (k+1)^3               (1)

so it's clear that S3 is a polynomial of finite degree in k.  Also, the
asymptotic growth rate obviously doesn't exceed the 4th power of k,
so we know that S3 can be expressed in the form 

          S3[N]  =  a*N^4 + b*N^3 + c*N^2 + d*N + e

for some constants a,b,c,d,e.  We immediately see that e must be zero 
to give S3[0] = 0.  Furthermore, from the relation (1) we have 

 a(N+1)^4 + b(N+1)^3 + c(N+1)^2 + d(N+1)  =  aN^4 + bN^3 + cN^2 + dN

                                               + N^3 + 3N^2 + 3N + 1

Expanding each of the binomials on the left hand side and collecting 
terms by powers of N, we find that a=1/4, b=1/2, c=1/4, and d=0. 
Thus, we have
                S3[N] = (1/4)N^4 + (1/2)N^3 + (1/4)N^2
 
The formulas for the sums of other powers can be derived similarly.
More generally, if f(k) is any polynomial function of k, we can easily
express the sum of f(k) over the first N integers by considering the 
sums of each separate term, which are pure sums of powers.