Stirling Numbers of the Second Kind, Bernoulli NumbersDate: 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/ |
Ask Dr. MathTM
© 1994-2002 The Math Forum
http://mathforum.org/dr.math/