Formula for Sum of First N squares
Date: 08/23/2001 at 15:59:11 From: mark fang Subject: Formula for the sum of the first N squares I found this question in your archives: Formula For the Sum Of the First N Squares http://mathforum.org/dr.math/problems/sandin2.20.98.html Can you show me how (1^2 + 2^2 + 3^2 + ... + N^2) becomes (N * (N + 1) * (2N + 1)) / 6 I was impressed by how Dr. Sam derived the formula, through the use of this cubing pattern: (x + 1)^3 = x^3 + 3x^2 + 3x + 1 However, I would like to know whether there are other methods to find the formula.
Date: 08/24/2001 at 14:39:21 From: Doctor Greenie Subject: Re: Formula for the sum of the first N squares Hi, Mark - I will show you a derivation of this formula in detail. But first, here is another page in the Dr. Math archives that presents the same problem a bit differently from either my solution or the one you read from Dr. Sam; it also references other pages where similar discussions are to be found: Sum of Consecutive Squares http://mathforum.org/dr.math/problems/robert.05.11.01.html ************************************** There is a general method by which you can derive the formula for the sum of the k-th powers of the first n positive integers. This is the method of finite differences. In fact, this method can be used to find the formula that generates any given sequence of numbers, as long as that formula is a polynomial function. Let me first demonstrate the method by starting with an arbitrary polynomial function, finding the sequence of values generated by that function, and then simulating the case where I am given that sequence of values and have to determine the polynomial function that generated it. I will choose (arbitrarily) the polynomial function n^2-3n+4 For n = 1, 2, 3, 4, 5, ..., the sequence of values generated by this function is 2, 2, 4, 8, 14, .... Now suppose I am given the sequence 2, 2, 4, 8, 14, ... and I want to find the polynomial function that generates the sequence. (Clearly, my answer should be the polynomial I started with: n^2-3n+4.) I use the numbers in the given sequence and the method of finite differences to determine the polynomial function. I start the method of finite differences by writing down the sequence of numbers I am given, leaving some space between them.... 2 2 4 8 14 Then, underneath this row of numbers, I write the differences between the successive terms; this is my row of "first differences" for the sequence: 2 2 4 8 14 0 2 4 6 These "first differences" are not all the same, so I next make another row consisting of the differences between the successive first differences (this is called the row of "second differences"): 2 2 4 8 14 0 2 4 6 2 2 2 In this row, all of the numbers are the same. According to the method of finite differences, if the row of n-th differences is constant, then the generating function is a polynomial of degree n. So, with the numbers in this row of second differences being all the same, we know that the generating function is a polynomial of degree 2. So our generating function is of the form f(n) = an^2+bn+c (1) We need to determine the values of a, b, and c. (In this case, of course, since we started with the known function, we know what the answer should be: a=1, b=-3, c=4.) With the first 5 terms of the sequence being given as 2, 2, 4, 8, and 14, we know f(1) = 2 f(2) = 2 f(3) = 4 f(4) = 8 f(5) = 14 But we also know from (1) that f(1) = a + b + c = 2 f(2) = 4a + 2b + c = 2 f(3) = 9a + 3b + c = 4 f(4) = 16a + 4b + c = 8 f(5) = 25a + 5b + c = 14 We have 5 equations relating the values of a, b, and c; we can use any 3 of these equations to find the values of a, b, and c. To keep the arithmetic as simple as possible, we choose the first three of them, since the coefficients in the last two are larger... a + b + c = 2 4a + 2b + c = 2 9a + 3b + c = 4 Eliminating the variable "c" between the first and second of these equations, and again between the second and third... 3a + b = 0 5a + b = 2 And eliminating the variable "b" between these two equations... 2a = 2 So we know a = 1 Then 3a + b = 0 3(1) + b = 0 3 + b = 0 b = -3 And finally a + b + c = 2 1 - 3 + c = 2 c = 4 We have determined that a=1, b=-3, and c=4, so our polynomial function, which generates the given sequence, is (as we knew before we started, in this case) f(n) = an^2+bn+c f(n) = n^2-3n+4 ***************************************** So much for our example to demonstrate the process. Now for finding the formula for the sum 1^2 + 2^2 + 3^2 + 4^2 + 5^2 + ... For n=1, the sum is 1^2 = 1 For n=2, the sum is 1^2+2^2 = 1+4 = 5 For n=3, the sum is 1^2+2^2+3^2 = 1+4+9 = 14 For n=4, the sum is 1^2+2^2+3^2+4^2 = 1+4+9+16 = 30 For n=5, the sum is 1^2+2^2+3^2+4^2+5^2 = 1+4+9+16+25 = 55 For n=6, the sum is 1^2+2^2+3^2+4^2+5^2+6^2 = 1+4+9+16+25+36 = 91 So the sequence we are working with is 1, 5, 14, 30, 55, 91, ... Let's try our method of finite differences on this sequence.... 1 5 14 30 55 91 4 9 16 25 36 5 7 9 11 2 2 2 The third row of differences is a constant, so the function we are looking for is a polynomial of degree 3: f(n) = an^3 + bn^2 + cn + d And we know (using the first four terms of the sequence) that f(1) = a + b + c + d = 1 f(2) = 8a + 4b + 2c + d = 5 f(3) = 27a + 9b + 3c + d = 14 f(4) = 64a + 16b + 4c + d = 30 We also know f(5)=55 and f(6)=91; however, we only need four equations to solve for the four unknowns a, b, c, and d. As in our earlier example, we successively eliminate variables from this set of equations: a + b + c + d = 1 8a + 4b + 2c + d = 5 27a + 9b + 3c + d = 14 64a + 16b + 4c + d = 30 7a + 3b + c = 4 19a + 5b + c = 9 37a + 7b + c = 16 12a + 2b = 5 18a + 2b = 7 6a = 2 Then we solve this equation for a and then substitute back in successive earlier equations to find the values of the other unknowns: a = 1/3 12a + 2b = 5 12(1/3) + 2b = 5 4 + 2b = 5 2b = 1 b = 1/2 7a + 3b + c = 4 7(1/3) + 3(1/2) + c = 4 c = 4 - 7/3 - 3/2 c = 1/6 a + b + c + d = 1 1/3 + 1/2 + 1/6 + d = 1 d = 0 So we have a=1/3, b=1/2, c=1/6, and d=0; so our polynomial function is f(n) = (1/3)n^3 + (1/2)n^2 + (1/6)n 2n^3 + 3n^2 + n f(n) = ----------------- 6 n*(2n^2 + 3n + 1) f(n) = ------------------- 6 n*(2n + 1)*(n+1) f(n) = ------------------- 6 *************************************** You can use this method to find the formula for the sum of the k-th powers of the first n positive integers, because the formula for the sum of the k-th powers of the first n positive integers is a polynomial of degree (k+1). As an example, the sequence formed by the sums of the cubes of the first n integers is 1, 9, 36, 100, 225, 441, ... (That is, 1^3=1; 1^3+2^3=9; 1^3+2^3+3^3=36; and so on....) You might try looking at this sequence and try to predict a formula (by noting that 1=1^2, 9=3^2, 36=6^2, 100=10^2, and so on). Then use the method of finite differences, as described and demonstrated above, to find the actual formula and see if your prediction is correct. Note that your prediction should be - and the actual formula will be - a polynomial of degree 4. I hope this response was not too much for you.... Write back if you have any further questions regarding your specific question, or if you have any questions about the method of finite differences. - Doctor Greenie, The Math Forum http://mathforum.org/dr.math/
Date: 08/24/2001 at 15:31:50 From: Wei Fang Subject: Re: Formula for the sum of the first N squares Hi, Dr. Greenie Thank you very much for your response. I found your explanation very clear and concise, consequently very helpful. Mark
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994-2013 The Math Forum