Finding Sum Formula using Sequences of Differences

Date: 06/28/98 at 20:05:12
From: Kyungsoo
Subject: Sum equation for higher powers

Hello!

What is the SUM FORMULA for 

     infinity (n)
    sum(sigma)   k^4
       k=1

For example, the sum formula for

     infinity(n)
    sum(sigma)   k     is n(n+1)/2
       k=1

The sum formulas I know are only up to k^3.

Then what are the sum formulas for higher powers of k?

Thanks,

KyungSoo

Date: 07/04/98 at 14:11:45
From: Doctor Floor
Subject: Re: Sum equation for higher powers

Hi KyungSoo,

Thank you for sending your question to Dr. Math. An interesting 
question it is!

I will show you how to find the formula for 

    n
   SUM k^4
   k=1

so you can do it for higher powers yourself. By the way, I'd rather 
not use the word infinity here, because you want n to be finite. If n 
were infinite, the sum would be infinite, too.

To make it a little easier for ourselves, I prefer to make the formula 
for
        n
S_n =  SUM k^4
       k=0

which doesn't make any difference at all, except that it starts with 
k=0 and is defined for n=0.

The formula that we will find for S_n will be a polynomial. The first 
thing we have to do is find out the degree of this polynomial. You can 
find the degree of this polynomial sequence by making so-called 
"sequences of differences." You make a sequence of differences by 
subtracting the consecutive numbers of the original sequence. As an 
example, I have taken the values of n^2 for n=1 to n=5. You'd begin by 
writing out these terms into the first line and then subtracting 
consecutive terms to write the second line.

   1  4  9  16  25  
     3  5  7   9    <-- (first) sequence of differences.
     ^
     |
     3 = 4-1

Now if you make a sequence of differences (SoD) of a polynomial 
sequence, then the degree of this SoD is one lower. In my example, you 
can see that the SoD is linear, so it is of first degree, whereas the 
original sequence was of second degree.

To see that this holds for the general case, suppose we have a 
sequence defined by P(n) = a*n^t + Q(n), where Q(n) is of lower degree 
than P(n). Then P(n+1) = a*(n+1)^t + Q(n+1) = a*n^t + R(n) + Q(n+1), 
where R(n) is the remainder of a*(n+1)^t when you have taken a*n^t 
out. R(n) is of degree t-1.

But for the sequence of differences (SoD(n)) of P(n) this means:
     SoD(n) = P(n+1) - P(n) = 
            = a*n^t + R(n) + Q(n+1) - (a*n^t + Q(n))
            = R(n) + Q(n+1) - Q(n).

So the degree of SoD(n) is lower than the degree of P(n), because R(n) 
and Q(n) (and Q(n+1)) are of lower degree than P(n). But we have not 
yet established that the degree is exactly one lower. It is exactly 
one lower, because Q(n+1)-Q(n) makes the SoD of Q(n), and thus Q(n+1)-
Q(n), of lower degree than Q(n)! So Q(n+1)-Q(n) is of degree t-2 or 
less. And since R(n) is of degree t-1, this must also be the case for 
SoD(n).

Back to the sequence S_n we are working on. This must be of fifth 
degree now, since S_n - S_(n-1) = n^4, so that the first SoD is 
clearly of fourth degree. You can also see that if you make 
consecutive SoD's - SoD's of SoD's, that is - then the fifth SoD is 
constant (degree zero). This is another way to see that our sequence 
must be polynomial of fifth degree. So let's calculate our sequence of 
sums of fourth power and check this out.

S_0 = 0^4 = 0
S_1 = S_0 + 1^4 = 0 + 1 = 1
S_2 = S_1 + 2^4 = 1 + 16 = 17
S_3 = S_2 + 3^4 = 17 + 81 = 98
S_4 = S_3 + 4^4 = 98 + 256 = 354
S_5 = S_4 + 5^4 = 354 + 625 = 979
S_6 = S_5 + 6^4 = 979 + 1296 = 2275

And now put these into the first line, and make five SoD's!

0    1    17    98    354    979    2275 <-- S_n
   1   16    81    256    625    1296
     15   65    175   369    671
       50    110   194    302
          60    84    108
             24    24      <-- 5th SoD is constant

Now that we know that the formula will be a fifth degree formula, it 
has to be of the form

S(n)= an^5 + bn^4 + cn^3 + dn^2 + en + f.

Since S(0)=0 (here is where I made it a little easier!), you know that 
f=0.

You could do two things now. The first is: make five equations with a, 
b, c, d, and e by taking different values for n. You could solve this, 
but it is a lot of work and no fun at all. The second thing you could 
do is use that S(n) - S(n-1) = n^4. That would mean that you'd have to 
expand S(n-1), which is not really fun, and then again you can make 
five equations from S(n) - S(n-1) = n^4 (from the fact that the 
coefficient with n^4 is 1, with n^3 is 0, etc.). I think these 
equations will work faster, though. So I choose this second option.

First expand 
S(n-1) = a(n-1)^5 + b(n-1)^4 + c(n-1)^3 + d(n-1)^2 + e(n-1).

Now we know that

    (n-1)^2 = n^2 - 2n + 1
    (n-1)^3 = n^3 - 3n^2 + 3n - 1
    (n-1)^4 = n^4 - 4n^3 + 6n^2 - 4n + 1
    (n-1)^5 = n^5 - 5n^4 + 10n^3 - 10 n^2 + 5n - 1

The coefficients come from Pascal's triangle.

This gives 

S(n-1) = an^5 + (-5a+b)n^4 + (10a-4b+c)n^3 + (-10a+6b-3c+d)n^2
          + (5a-4b+3c-2d+e)n + (-a+b-c+d-e).

So

S(n) - S(n-1) = (5a)n^4 + (-10a+4b)n^3 + (10a-6b+3c)n^2
                 + (-5a+4b-3c+2d)n + (a-b+c-d+e).

Since this has to equal n^4, you get the following equations:

                  5a = 1
           -10a + 4b = 0
       10a - 6b + 3c = 0
  -5a + 4b - 3c + 2d = 0
   a - b + c - d + e = 0

Solving these is quickly done, when just going down one after one: 
a = 1/5, b = 1/2, c = 1/3, d = 0, e = -1/30.

So that would give

S(n) = (1/5)n^5 + (1/2)n^4 + (1/3)n^3 - (1/30)n.

I'll leave it for you to check this one, and to make formulas for 
higher powers in this way.

Thank you for letting me experience this solution - I did not know 
beforehand where it would end, and I was delighted by the simple 
result. I hope you like the answer, too.

If you have other math questions, please send them to Dr. Math!

Best regards,

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