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