Associated Topics || Dr. Math Home || Search Dr. Math

### 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
```
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
Math Forum Home || Math Library || Quick Reference || Math Forum Search