Closed form for sums of k^th powers of numbers

We know the closed form solution of sum of the first n natural numbers - n(n+1)/2. This has a cute proof : compute the sum twice as follows.

1 + 2   +  3  + ... + n-2 + n-1 + n +
n + n-1 + n-2 + ... + 3   + 2   + 1

There are n columns each summing up to n+1. Hence the original sum is n(n+1)/2.

We may know the closed form for the sum of squares of the first n numbers, or their cubes. What about arbitrary natural number powers of integers?

Here is a heuristic: sum of the k^th powers of the first n numbers can be approximated by the integral of x^k dx. This is a polynomial of degree k+1.

Heuristically, we will assume that the sum of the k^th powers of the first n numbers is also a polynomial of degree k+1. We will not prove this, but assume this to be correct.So, assume that the answer is

            k+1      k 
S(x) = a   x   + a  x  + ... + a  x + a .
        k+1       k             1      0

A polynomial of degree k+1 is uniquely determined by any set of k+1 evaluations. So assume we have

S(0) = a 
        0

S(1) = a   + a + ... + a + a
        k+1   k         1   0

            k+1
S(2) = a   2    + ... + a  2 + a
        k+1              1      0

...
                 k+1
S(k+1) = a   (k+1)    + ... + a (k+2) + a
          k+1                  1         0

This is a system of linear equations involving the variables

a   , ..., a
 k+1        0

A solution to this system will give a closed form solution to the problem.