Summing n^kDate: 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/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/