Drexel dragonThe Math ForumDonate to the Math Forum

Ask Dr. Math - Questions and Answers from our Archives
_____________________________________________
Associated Topics || Dr. Math Home || Search Dr. Math
_____________________________________________

Stirling Numbers of the Second Kind, Bernoulli Numbers


Date: 05/29/2001 at 13:01:13
From: Mahdi
Subject: Formula

Sk = 1^k+2^K+3^k+...+n^k.
Find Sk as a formula.

S1=1^1+2^1+3^1+...+n^1=1/2 n(n+1) 
S2=1^2+2^2+3^2+...+n^2=1/6 n(n+1)(2n+1)
S3=1^3+2^3+3^3+...+n^3=1/4 n^2(n+1)^2
S4=1^4+2^4+3^4+...+n^4=1/30 n(n+1)(2n+1)(3n^2+3n-1)

("/" stands for division)

Yours truly,
Mahdi Soltani


Date: 05/29/2001 at 15:12:23
From: Doctor Rob
Subject: Re: Formula

Thanks for writing to Ask Dr. Math, Mahdi.

The general formula involves Stirling Numbers of the Second Kind.  
Write

          k
   m^k = SUM S2(k,j)*C(m,j)*j!,
         j=1

where C(m,j) are binomial coefficients and S2(k,j) are integer 
constants, called Stirling Numbers of the Second Kind. They can be 
computed somewhat like binomial coefficients by using the recurrence 
relation, for all j and k positive integers,

   S2(k,1) = 1,
   S2(k,j) = 0 if j > k,
   S2(k+1,j) = j*S2(k,j) + S2(k,j-1).

Here is a table of S2(k,j)

   k \ j | 1    2    3     4     5    6    7    8
   ------+---------------------------------------
     1   | 1    0    0     0     0    0    0    0
     2   | 1    1    0     0     0    0    0    0
     3   | 1    3    1     0     0    0    0    0
     4   | 1    7    6     1     0    0    0    0
     5   | 1   15   25    10     1    0    0    0
     6   | 1   31   90    65    15    1    0    0
     7   | 1   63  301   350   140   21    1    0
     8   | 1  127  966  1701  1050  308   28    1

I don't know a closed-form expression for these numbers.

Then

    n         n   m
   SUM m^k = SUM SUM S2(k,j)*C(m,j)*j!,
   m=1       m=1 j=1

              k   n
           = SUM SUM S2(k,j)*C(m,j)*j!,
             j=1 m=j

              k              n
           = SUM S2(k,j)*j!*SUM C(m,j),
             j=1            m=j

              k             n-j
           = SUM S2(k,j)*j!*SUM C(r+j,j),
             j=1            r=0

    n         k
   SUM m^k = SUM S2(k,j)*j!*C(n+1,j+1).
   m=1       j=1

This is the simplest formula I know. For kth powers, there are k terms 
in the sum.

For example, if we let k = 7, then

    n         7
   SUM m^7 = SUM S2(7,j)*j!*C(n+1,j+1),
   m=1       j=1

           = 1*1!*(n+1)n*/2! + 63*2!*(n+1)*n*(n-1)/3! +
               301*3!*(n+1)*n*(n-1)*(n-2)/4! +
               350*4!*(n+1)*n*(n-1)*(n-2)*(n-3)/5! +
               140*5!*(n+1)*n*(n-1)*(n-2)*(n-3)*(n-4)/6! +
               21*6!*(n+1)*n*(n-1)*(n-2)*(n-3)*(n-4)*(n-5)/7! +
               1*7!*(n+1)*n*(n-1)*(n-2)*(n-3)*(n-4)*(n-5)*(n-6)/8!,

           = (n+1)*n*(1/2 + 63*[n-1]/3 + 301*[n-1]*[n-2]/4 +
               350*[n-1]*[n-2]*[n-3]/5 +
               140*[n-1]*[n-2]*[n-3]*[n-4]/6 +
               21*[n-1]*[n-2]*[n-3]*[n-4]*[n-5]/7 +
               [n-1]*[n-2]*[n-3]*[n-4]*[n-5]*[n-6]/8),

           = (n+1)*n*(1/2 + 21*[n-1] + 301*[n-1]*[n-2]/4 +
               70*[n-1]*[n-2]*[n-3] +
               70*[n-1]*[n-2]*[n-3]*[n-4]/3 +
               3*[n-1]*[n-2]*[n-3]*[n-4]*[n-5] +
               [n-1]*[n-2]*[n-3]*[n-4]*[n-5]*[n-6]/8),

           = n^8/8 + n^7/2 + 7*n^6/12 - 7*n^4/24 + n^2/12,

           = (1/24)*n^2*(n+1)^2*(3*n^4+6*n^3-n^2-4*n+2).

The only expression I can find for the coefficients of the powers
of n involves a triple sum of Stirling Numbers of the First Kind,
Stirling Numbers of the Second Kind, and binomial coefficients.

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


Date: 06/08/2001 at 15:13:47
From: Doctor Rob
Subject: Re: Formula

Hello, Mahdi - I have found more information on your problem:

There is also a formula involving Bernoulli Numbers:

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

        = n^(p+1)/(p+1) + n^p/2 -
            [p/2]
             SUM ([-1]^r/[2*r])*C(p,2*r-1)*B(2*r)*n^(p-2*r+1).
             r=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]!). This 
formula tells you the coefficients of each power of n in the formula 
sought.

The Bernoulli Numbers B(2*r) are rational numbers which can be 
calculated by

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

or by

            r-1
   B(2*r) = SUM C(2*r,2*i-2)*B(2*i),
            i=1
   B(2) = 1/6,
   B(4) = 1/30,
   B(6) = 1/42,
   ...

or by

               infinity
   x/(e^x-1) =   SUM   (-1)^(r/2)*B(r)*x^r/r!.
                 r=0

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

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

Here is an additional observation.

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

                        p-1                      n
              n^(p+1) - SUM (-1)^(p-i)*C(p+1,i)*SUM i^j
    n                   i=0                     i=1
   SUM  i^p = -----------------------------------------.
   i=1                            p + 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:

              n          
   n^(p+1) = SUM [i^(p+1)-(i-1)^(p+1)],
             i=1

              n             p+1
           = SUM [i^(p+1) - SUM (-1)^(p-i+1)*C(p+1,i)*i^j],
             i=1            i=0

              n    p
           = SUM  SUM (-1)^(p-j)*C(p+1,j)*i^j,
             i=1  j=0

              p    n
           = SUM  SUM (-1)^(p-j)*C(p+1,j)*i^j,
             j=0  i=1

              p                       n
           = SUM (-1)^(p-j)*C(p+1,j)*SUM i^j,
             j=0                     i=1

                       n        p-1                      n
           = C(p+1,p)*SUM i^p + SUM (-1)^(p-j)*C(p+1,j)*SUM i^j,
                      i=1       j=0                     i=1

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

As an example, let p = 4.  Then

                    3                     n
             n^5 - SUM (-1)^(4-j)*C(5,j)*SUM i^j
    n              j=0                   i=1
   SUM i^4 = -----------------------------------,
   i=1                       5

             = (n^5 -
                  C(5,0)*[n] +
                  C(5,1)*[n*(n+1)/2] -
                  C(5,2)*[n*(n+1)*(2*n+1)/6] +
                  C(5,3)*[n^2*(n+1)^2/4])/5,
             = [n^5 - n + 5*n*(n+1)/2 - 10*n*(n+1)*(2*n+1)/6 +
                  10*n^2*(n+1)^2/4]/5,
             = [n^5 - n + 5*n*(n+1)/2 - 5*n*(n+1)*(2*n+1)/3 +
                  5*n^2*(n+1)^2/2]/5,
             = [n^5 - n + 5*n*(n+1)/2 - 5*n*(n+1)*(2*n+1)/3 +
                  5*n^2*(n+1)^2/2]/5,
             = n*(n+1)*(n^3-n^2+n-1+5/2-10/3*n-5/3+5/2*n^2+5/2*n)/5,
             = n*(n+1)*(n^3+3/2*n^2+1/6*n-1/6)/5,
             = n*(n+1)*(6*n^3+9*n^2+n-1)/30,
             = n*(n+1)*(2*n+1)*(3*n^2+3*n-1)/30.

- Doctor Rob, The Math Forum
  http://mathforum.org/dr.math/   
    
Associated Topics:
College Number Theory
High School Number Theory

Search the Dr. Math Library:


Find items containing (put spaces between keywords):
 
Click only once for faster results:

[ Choose "whole words" when searching for a word like age.]

all keywords, in any order at least one, that exact phrase
parts of words whole words

Submit your own question to Dr. Math

[Privacy Policy] [Terms of Use]

_____________________________________
Math Forum Home || Math Library || Quick Reference || Math Forum Search
_____________________________________

Ask Dr. MathTM
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/