Sum of Squares Derivation
Date: 11/30/2002 at 21:44:03 From: Jeremy Subject: Sum of squares derivation In class, I was given the chessboard squares problem mentioned in your archives: How many total squares are there in a chessboard of a given dimension (for example a 2x2 chessboard has 5 total squares and a 3x3 has 14). I figured out myself that the answer is the sum of squares up to the number of squares on one side of the board. Your archives showed me that this can be expressed by the formula: (n(n+1)+(2n+1))/6. Checkerboard Squares http://mathforum.org/library/drmath/view/56167.html In your archives I have found the inductive proof of the formula Formula For the Sum Of the First N Squares http://mathforum.org/library/drmath/view/56920.html This proof begins with knowing the formula already. How can you derive the formula without knowing what it is? I guess I am looking for a derivation instead of a proof. Thanks very much for any help you can give.
Date: 12/01/2002 at 23:40:17 From: Doctor Peterson Subject: Re: Sum of squares derivation You copied the formula incorrectly; it's S = n(n+1)(2n+1)/6 I can think of several ways to derive this formula without knowing the formula already. None is merely an automatic algebraic derivation where you can just turn the crank and get the answer without any insight; one requires recognizing that the answer will be a polynomial, another uses a neat trick, and another requires some incredible visualization of three-dimensional shapes. Yet another requires that you connect the series with tetrahedral numbers. I'd like to got through the first two of these for you. This page gives one method and refers you to some others: Sum of Consecutive Squares http://mathforum.org/library/drmath/view/56982.html First, the most straighforward method uses "finite differences," which you can read about in more detail here: Method of Finite Differences http://mathforum.org/library/drmath/view/53223.html If you take the differences between successive terms in the sequence of sums of squares, and then take the differences between those, and so on, you get this: 0 1 5 14 30 <-- our sequence 1 4 9 16 <-- the squares you are summing 3 5 7 <-- the differences of those 2 2 0 The fact that EVERY term in this fourth difference is 0 tells us that the answer will be a third degree polynomial. One neat way to find what it is is to compare our differences with those obtained from monomials: n^3: 0 1 8 27 64 1 7 19 37 6 12 18 6 6 0 n^2: 0 1 4 9 1 3 5 2 2 0 n^1: 0 1 2 1 1 0 To get the third row of our differences, we will need 1/3 of the differences for n^3. If we subtract 1/3 of each number in that triangle from ours, we can see what's left; we only need to look at the first term in each row: S - n^3/3: 0 - 0/3 = 0 1 - 1/3 = 2/3 3 - 6/3 = 1 2 - 6/3 = 0 Now we have the third row zero, and can compare with the differences for n^2. We will need 1/2 of the differences for n^2; if we subtract that off, we get S - (n^3/3 + n^2/2): 0 - 0/2 = 0 2/3 - 1/2 = 1/6 1 - 2/2 = 0 Now the second row is zero, and we compare with the differences for n^1; this time we subtract 1/6 of each difference for n, and have S - (n^3/3 + n^2/2 + n/6): 0 - 0/6 = 0 1/6 - 1/6 = 0 Everything is now zero, so we don't need a constant term; we find that S = n^3/3 + n^2/2 + n/6 = (2n^3 + 3n^2 + n)/6 and we can factor this to get the final form: S = n(n+1)(2n+1)/6 The second method uses a "telescoping" series of differences of cubes. That is shown in one of the pages I referred to; I want to show a variation on that. First note that a sum of the form (1 - 0) + (8 - 1) + (27 - 8) + ... + (n^3 - (n-1)^3) will collapse, since we have 1 in the first term and -1 in the second, 8 in the second and -8 in the third, and so on, to n^3 - 0 So if we can express x^2 in terms of such differences, we can find the sum very easily. Notice now that x^3 - (x-1)^3 = x^3 - (x^3 - 3x^2 + 3x - 1) = 3x^2 - 3x + 1 and x^2 - (x-1)^2 = x^2 - (x^2 - 2x + 1) = 2x - 1 We can use these to write x^2 = ([x^3 - (x-1)^3] + 3x - 1)/3 and x = ([x^2 - (x-1)^2] + 1)/2 We can plug the second into the first of these to get x^2 = ([x^3 - (x-1)^3] + 3([x^2 - (x-1)^2] + 1)/2 - 1)/3 [x^3 - (x-1)^3]/3 + [x^2 - (x-1)^2]/2 - 1/6 Now, summing this for x = 1 to x = n, we get sum(x^2) = sum([x^3 - (x-1)^3]/3 + [x^2 - (x-1)^2]/2 - 1/6) = sum[x^3 - (x-1)^3]/3 + sum[x^2 - (x-1)^2]/2 - sum(1/6) = [n^3 - 0^3]/3 + [n^2 - 0^2]/2 - n/6 = n^3/3 + n^2/2 - n/6 = (2n^3 + 3n^2 - n)/6 as before. If you have any further questions, feel free to write back. - Doctor Peterson, The Math Forum http://mathforum.org/dr.math/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994-2015 The Math Forum