Associated Topics || Dr. Math Home || Search Dr. Math

### 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.

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/

Associated Topics:
High School Number Theory
High School Permutations and Combinations
High School Sequences, Series

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