COME ON CODE ON

A blog about programming and more programming.

Sum of First n m-th Powers

with 2 comments

This is going to be long even without the proof.
The sum of the first n m-th powers is given by the formula :

sum of first n m-th powers

sum of first n m-th powers

where S2 is Stirling numbers of the Second Kind :

m\k| 1    2    3    4    5    6
——————————-
 1  | 1
 2  | 1    1
 3  | 1    3    1
 4  | 1    7    6    1
 5  | 1   15   25   10    1
 5  | 1   31   90   65   15    1

given by the recurrence relation :

for m >= 1,

S2(m,0) = 0,
S2(m,1) = 1,
S2(m,k) = 0 for all all k > m,
S2(m+1,k) = S2(m,k-1) + k*S2(m,k).

and f(x,k) = x*(x-1)*(x-2)*…*(x-k+1).

Let us take two examples :

T(2,n) = S2(2,1)*f(n+1,2)/2 + S2(2,2)*f(n+1,3)/3,
          = 1*(n+1)*n/2 + 1*(n+1)*n*(n-1)/3,
          = n*(n+1)*(1/2 + [n-1]/3),
          = n*(n+1)*(1/2 + n/3 – 1/3),
          = n*(n+1)*(2*n+1)/6.
and

T(4,n) = S2(4,1)*f(n+1,2)/2 + S2(4,2)*f(n+1,3)/3 +
              S2(4,3)*f(n+1,4)/4 + S2(4,4)*f(n+1,5)/5,
          = 1*(n+1)*n/2 + 7*(n+1)*n*(n-1)/3 +
              6*(n+1)*n*(n-1)*(n-2)/4 +
              1*(n+1)*n*(n-1)*(n-2)*(n-3)/5,
          = n*(n+1)*(1/2 + 7*[n-1]/3 + 3*[n-1]*[n-2]/2 +
              [n-1]*[n-2]*[n-3]/5),
          = n*(n+1)*(1/2 + 7*[n-1]/3 + 3*[n^2-3*n+2]/2 +
              [n^3-6*n^2+11*n-6]/5),
          = n*(n+1)*(1/2 + 7*n/3 – 7/3 + 3*n^2/2 – 9*n/2 + 3 +
              n^3/5 – 6*n^2/5 + 11*n/5 – 6/5),
          = n*(n+1)*(n^3/5 + 3*n^2/10 + n/30 – 1/30),
          = 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.

Try higher powers for yourself.
-fR0D

Advertisements

Written by fR0DDY

February 26, 2009 at 9:32 AM

Posted in Maths

Tagged with , , ,

2 Responses

Subscribe to comments with RSS.

  1. Hello. Could you tell me where I can find a full proof of this formula?
    Thanks,
    Howard

    Howard Walker

    September 13, 2012 at 2:49 AM

    • See problem solving strategies, chapter 5-Enumerative combinatorics

      Masum

      October 20, 2012 at 4:40 PM


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: