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

### Sum of Powers of 2

Date: 08/28/2001 at 01:09:39
From: Amir Milbes
Subject: Sums of powers

Hi!

I read and understood the method on how to derive a general formula
for the sum of consecutive integers.

(<>  1 + 2 + 3 + ... + n = S(n) = [n(n+1)]/2

Basically I did the following :

1 + 2 + 3 + ...+ n = S(n)
n + (n-1) + (n-2) + ... + 3 + 2 + 1 = S(n)
--------------------------------------------
(n+1)+(n+1)+ ... + (n+1) = 2S(n)
n(n+1) = 2S(n)
[n(n+1)]/2 = S(n).

Then I wanted to derive a formula for the sum of powers of 2:

1^2 + 2^2 + 3^2 + ... + n^2 = S(n)

This is were I get stuck. I tried the same method that I had used on
consecutive integers but it did not seem to work, at least it got me
lost. I don't know where to find a book that shows the  DERIVATION  of
such formulas.

I do have a precalculus book that shows the formulas for powers of 2,
3, 4, and even 5, but it does not show how they arrived at the
formula. I want to see how the formula was derived.

Thanks.
Sincerely,
Amir Milbes

Date: 08/28/2001 at 10:19:50
From: Doctor Rob
Subject: Re: sums of powers

Thanks for writing to Ask Dr. Math, Amir.

This is done in the following way. Define, recursively,

f(x,0) = 1,
f(x,k+1) = f(x,k)*(x-k), k >= 0.

Then one has the equation

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

This is called the "k-th falling factorial of x."  Notice that

f(x+1,k+1) - f(x,k+1) = (x+1)*f(x,k) - f(x,k)*(x-k),
= ([x+1]-[x-k])*f(x,k).
= (k+1)*f(x,k),
f(x,k) = [f(x+1,k+1)-f(x,k+1)]/[k+1].

Now write the powers of x in terms of f(x,k) for various k's:

m
x^m = SUM S2(m,k)*f(x,k),
k=0

for some constants S2(m,k). In particular,

x^1 = 1*f(x,1),
x^2 = 1*f(x,2) + 1*f(x,1),
x^3 = 1*f(x,3) + 3*f(x,2) + 1*f(x,1),
x^4 = 1*f(x,4) + 7*f(x,3) + 6*f(x,2) + 1*f(x,1),

and so on. These constant coefficients S2(m,k) are called the Stirling
Numbers of the Second Kind. They are always positive integers, and
satisfy the following recursion relations:

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

You can prove these formulas by using Mathematical Induction. They
allow one to compute the Stirling Numbers of the Second Kind in a
similar way to computing Binomial Coefficients using Pascal's
Triangle.

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

For example, 90 = 15 + 3*25, and 65 = 25 + 4*10.

(There are also Stirling Numbers of the First Kind S1(m,k), which are
the coefficients you get when expressing f(x,m) in terms of the powers
x^k for k = 1, 2, ..., m.)

Now we can use the material above to compute the sum

n
T(m,n) = SUM x^m,
x=1

n   m
= SUM SUM S2(m,k)*f(x,k),
x=1 k=1

m           n
= SUM S2(m,k)*SUM f(x,k),
k=1         x=1

m           n
= SUM S2(m,k)*SUM [f(x+1,k+1)-f(x,k+1)]/[k+1],
k=1         x=1

m                 n
= SUM S2(m,k)/(k+1)*SUM f(x+1,k+1) - f(x,k+1).
k=1               x=1

Now the inner sum is a collapsing or telescoping sum, and f(1,k+1) = 0
for all k >= 1, so

m
T(m,n) = SUM S2(m,k)/(k+1)*[f(n+1,k+1)-f(1,k+1)],
k=1

m
T(m,n) = SUM S2(m,k)*f(n+1,k+1)/(k+1).
k=1

This is the formula which you can use to find the sum of the first
m n-th powers. For example, when m = 2, you get

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.

As another example, when m = 4, you get

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.

These should agree with the formulas in your book.

- Doctor Rob, The Math Forum
http://mathforum.org/dr.math/

Associated Topics:
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