Wednesday 19 December 2012

Some Notes on the Sum of Squares of the Integers

12+22+32+...+n2 = (n)(n+1)(2n+1)/6

Recently I have been talking about the pre-calc use of the series formed by the powers of integers, and I wanted to focus a little on the one above for the sums of the squares of the integers, a bit of the history of the relation, and a little history about couple of problems related to the identity.  When I was first confronted with the expression the 2n+1 term seemed strangely out of place to me, and over the years it seems that students, and others also found the sequence to be a little quirky. 
The traditional high school approach tends to be to advise the student to memorize the relationship, and then prove it with induction.  I find great joy in inductive proofs, and think they are a wonderful tool, but I don't think they either a) help in remembering the identity, or b) make it understandable why the 2n+1 term pops up.

I'm not sure my way of explaining how one might come up with the identity from scratch in a way that ties together logically for most students is any more of an explanation for 2n+1, but it does seem to supply students with a way to produce the sum from scratch.
It is unknown who first came up with the identity, but it was certainly known, and beautifully used, by Archimedes.  Archimedes used the sums of squares to find the area inside a spiral.

It was expressed pretty much the way we do it now without the notation by several of the Arabic language scholars, and Fibonacci gives the sum in his Liber Abacci using the first ten integers and gives 10 (11)21/6 as the solution.  Actually he divides by both six and one to make a point as he follows with a method for finding the sums of the squares of the odd integers.
Fibonacci explains that you multiply by n (in his example 10), times its successor (n+1) times their sum .... aha, a reason for the 2n+1 and divide by six, and then by one because one is the difference in ten and eleven.

For the sum of squares of the odd numbers up through nine he offers the same sort of approach; you multiply the last number (9) times its successor (in this case 11) times their sum (20) and then divide by six, and then by two because it is the difference between the numbers.  He goes on to apply his method to the sum of squares of general arithmetic sequences,but I digress. Read the master at your leisure.  As was common for the time, no general reason is given for the method, and no proof other than the examples given was provided.

When I was pressed to try and make this understandable to high school students, I returned to the ancient Pythagorean knowledge that the square numbers were the sum of two successive triangular numbers.

In the image the 4th and 5th triangular numbers are shown combined to make the square of five.
I chose the triangular numbers because it is easy to show that the triangular numbers can be expressed as (N+1)C 2 {the fourth triangular number, 10, is given by 5C2 for example} and read off Pascal's triangle, a "friendly" mystery to most high school students.
More importantly, if you sum the first n triangular number they can be easily expressed as (N+2)C3. The sum of the first four triangular numbers, 1 + 3 + 6 + 10 = 20 is equal to (4+2) C 3.

Now once we have the fact that every square is the sum of two consecutive triangular numbers and that triangular numbers are easy to sum using combinations, we can proceed to show the squares broken into triangular numbers as below:

1 ................. 1
4 .................. 3 + 1
9 .................. 6 + 3
16 .................10 + 6
30 ................. 20 + 10

So the sum of the first four squares is given by (4+2)C 3 + (3+2)C 3

We can generalize this using simple algebra to produce

12+22+32+...+n2 = (n+2)C 3 + (n+1)C 3
= (n+2)(n+1)n/6 + (n+1)(n)(n-1)/6
and factoring out the (n+1) and n in both terms we get

= (n+1)(n) ((n+2)+(n-1) ) /6 (ahhhh see the 2n+1 now chiledren???)

= n(n+1)(2n+1)/6

And then it finally made its way into recreational mathematics.
As far as I can find the first use of the sum of squares in recreational mathematics came about because of a question by the famous Sir Walter Raleigh to his mathematical aide, Thomas Harriot. He supposedly asked Harriot around 1600 how he could quickly compute the number of cannonballs in a stack in the form of a square pyramid (like the one at top). Harriot gave him the answer, but the interest in the problem led to a second question, is there any square pyramidal number which is itself a square? Of course 1 is a trivial example, but were there more? It turns out that there was, at least one more. It turns out that if you sum the first 24 squares, you get a total which is also a square. But were there any more?
The famous recreational mathematician, Edouard Lucas (father of the Towers of Hanoi puzzle) conjectured in 1875 conjectured that there were no others, but the proof waited until G. N. Watson found a complete proof in 1918.

Within another decade, the famous son of Sam Loyd, also named Sam, released the first puzzle in which you were challenged to count the total number of squares in a square grid.

In the image above it is easy to see the relation to the sum of squares; there are nine squares that are 1x1, 4 that are 2x2, and1 that is 3x3, for a total of 32+22+12 = 13 squares.  (Of course Loyd's puzzle was somewhat more difficult).

If anyone knows another classic puzzle that invokes the sum of squares I would love to know about it. 

A related follow up post prompted by the comment below of Joshua Zucker.


Joshua Zucker said...

This is beautiful stuff! I'm not finding any other sum of squares puzzles popping to the front of my mind but I'm sure something will occur to me later.

Meanwhile, for a non-sum-of-squares question, what happens in your Loyd puzzle if you replace the grid of lines with a grid of dots? Now there are more squares ... but how many?

I have several formulas for the answer and I had a great deal of fun explaining where they come from in more combinatorial ways (like you did with the triangular numbers approach to summing the squares as the sum of two tetrahedral numbers).

I'd still like to see something here involving the 2n+1 as an actual dimension of some 3D object that relates to the volume of the stack of balls, rather than as something that appears algebraically, though your approach here is still so much better than the "guess a formula plus prove it by induction" approach.

Something like for example!

Anonymous said...

This website has very good content. So I am sure this website will form the well-known in the future.