Summing n^k

Date: 11/24/98 at 10:15:59
From: Kijjaz
Subject: SIGMA of n^c

We know:

   Sigma (n^0) = n 
   Sigma (n^1) = n(n+1)/2
   Sigma (n^2) = n(n+1)(2n+1)/6
   Sigma (n^3) = (n(n+1)/2)^2
   ...

Is there an easy solution to find the result of Sigma (n^k), where k is 
a positive integer, like the right side of the equations above?

Thank you.

Date: 11/25/98 at 10:31:45
From: Doctor Rob
Subject: Re: SIGMA of n^c

No, there is not.

The next few formulas look like this:

   Sigma n^4 = n*(n+1)*(2*n+1)*(3*n^2+3*n-1)/30
   Sigma n^5 = n^2*(n+1)^2*(2*n^2+2*n-1)/12
   Sigma n^6 = n*(n+1)*(2*n+1)*(3*n^4+6*n^3-3*n+1)/42
   Sigma n^7 = n^2*(n+1)^2*(3*n^4+6*n^3-n^2-4*n+2)/24

The simplest formula I know involves Stirling Numbers of the Second 
Kind S(p,k). They satisfy the identity:

           p
   x^p = Sigma S(p,k)*k!*C(x,k)
          k=1

where x is an indeterminate. S(p,1) = 1 = S(p,p) for all p >= 1, and
there is a recursion they satisfy:

   S(p,k) = S(p-1,k-1) + k*S(p-1,k), p >= 1, 1 <= k <= p

This allows you to compute the numbers explicitly in short order to as
large a value of p as you might want, similarly to Pascal's Triangle 
for computing binomial coefficients.

Then, summing over x = 1, 2, ..., n:

     n           p               n
   Sigma x^p = Sigma S(p,k)*k!*Sigma C(x,k)
    x=1         k=1             x=1

                 p
             = Sigma S(p,k)*k!*C(n+1,k+1)
                k=1

There is also a formula involving Bernoulli Numbers:

     n
   Sigma x^p = n^(p+1)/(p+1) + n^p/2 + (1/2)*C(p,1)*B(1)*n^(p-1) -
    x=1        (1/4)*C(p,3)*B(3)*n^(p-3) + (1/6)*C(p,5)*B(5)*n^(p-5) - 
                ...

             = n^(p+1)/(p+1) + n^p/2 -
                 [p/2]
                 Sigma ([-1]^i/[2*i])*C(p,2*i-1)*B(2*i-1)*n^(p-2*i+1)
                  i=1

The last term involves either n^2 or n, depending on whether p is odd 
or even. C(p,k) are the binomial coefficients p!/(k!*[p-k]!).

The Bernoulli Numbers B(i) are rational numbers that can be calculated 
by:

B(i) = 2*(2*i)!/([4^i-1]*Pi^[2*i])*(1/1^(2*i)+1/3^(2*i)+1/5^(2*i)+...)

or by:

                i
   B(2*i+1) = Sigma C(2*i+2,2*k)*B(2*k+1),
               k=0
   B(1) = 1/6
   B(3) = -1/30
   ...

or by:

               infinity
   x/(e^x-1) =  Sigma B(i)*x^i/i!
                 i=0

They also appear in the Maclaurin series for the tangent of x:

            infinity
   tan(x) =  Sigma (-1)^(r-1)*4^r*(4^r-1)*B(2*r-1)*x^(2*r-1)/(2*r)!
              r=1

This is a question often asked, and involves some very complicated and
interesting mathematics.

Here is an additional observation:

If you know all the formulas for smaller powers, you can find the next
one as follows:

                          q-1                        k
               k^(q+1) - Sigma (-1)^(q-i)*C(q+1,i)*Sigma n^i
     k                    i=0                       n=1
   Sigma n^q = ---------------------------------------------
    n=1                            q + 1

Here C(a,b) = a!/(b!*[a-b]!) is a binomial coefficient.

This is derived by using the following telescoping sum and the 
Binomial Theorem:

               k          
   k^(q+1) = Sigma [n^(q+1)-(n-1)^(q+1)]
              n=1

               k               q+1
           = Sigma [n^(q+1) - Sigma (-1)^(q-i+1)*C(q+1,i)*n^i]
              n=1              i=0

               k     q
           = Sigma Sigma (-1)^(q-i)*C(q+1,i)*n^i
              n=1   i=0

               q     k
           = Sigma Sigma (-1)^(q-i)*C(q+1,i)*n^i
              i=0   n=1

               q                         k
           = Sigma (-1)^(q-i)*C(q+1,i)*Sigma n^i
              i=0                       n=1

                        k          q-1                        k
           = C(q+1,q)*Sigma n^q + Sigma (-1)^(q-i)*C(q+1,i)*Sigma n^i
                       n=1         i=0                       n=1

and now solve for the summation in the first term on the right, using 
the fact that C(q+1,q) = q + 1.

As an example, let q = 4. Then:

                       3                       k
               k^5 - Sigma (-1)^(q-i)*C(5,i)*Sigma n^i
     k                i=0                     n=1
   Sigma n^4 = ---------------------------------------
    n=1                          5

             = (k^5 -
                  C(5,0)*[k] +
                  C(5,1)*[k*(k+1)/2] -
                  C(5,2)*[k*(k+1)*(2*k+1)/6] +
                  C(5,3)*[k^2*(k+1)^2/4])/5

             = [k^5 - k + 5*k*(k+1)/2 - 10*k*(k+1)*(2*k+1)/6 +
                  10*k^2*(k+1)^2/4]/5

             = [k^5 - k + 5*k*(k+1)/2 - 5*k*(k+1)*(2*k+1)/3 +
                  5*k^2*(k+1)^2/2]/5

             = [k^5 - k + 5*k*(k+1)/2 - 5*k*(k+1)*(2*k+1)/3 +
                  5*k^2*(k+1)^2/2]/5

             = k*(k+1)*(k^3-k^2+k-1+5/2-10/3*k-5/3+5/2*k^2+5/2*k)/5

             = k*(k+1)*(k^3+3/2*k^2+1/6*k-1/6)/5

             = k*(k+1)*(6*k^3+9*k^2+k-1)/30

             = k*(k+1)*(2*k+1)*(3*k^2+3*k-1)/30

- Doctor Rob, The Math Forum
  http://mathforum.org/dr.math/