Drexel dragonThe Math ForumDonate to the Math Forum

Ask Dr. Math - Questions and Answers from our Archives
_____________________________________________
Associated Topics || Dr. Math Home || Search Dr. Math
_____________________________________________

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/ 
Associated Topics:
High School Sequences, Series

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

[Privacy Policy] [Terms of Use]

_____________________________________
Math Forum Home || Math Library || Quick Reference || Math Forum Search
_____________________________________

Ask Dr. MathTM
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/