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/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.