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

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

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
Math Forum Home || Math Library || Quick Reference || Math Forum Search