## Tuesday, August 25, 2009

### Sum of squares

I got interested in learning more about Archimedes. In particular, I was amazed by his derivation of the formula for the volume of a sphere. Actually he was pretty proud of it himself---according to legend and confirmed by Cicero's testimony his gravestone "was surmounted by a sphere and a cylinder."

So that's where I'm headed, but in order to get there, we need to start with a simpler problem. What is the sum of all the values n2 for n = 1 to n = k? The squares and the sum go like this:

 `1 14 59 1416 3025 5536 9149 14064 204`

It is hard to see the pattern, so let's look up the answer, the formula is:

sum of squares = k * (k+1) * (2k+1) / 6

There is a neat proof by induction in the post. We assume that the formula is correct for n = k and then prove that if so, it is also true for n = k+1. We must also prove that it works for the "base case", n = 1, but that is self-evident.

We have:

 `n = k Σ n2 = k * (k+1) * (2k+1) / 6n = 1`

To find the sum of squares for k+1, we add (k+1)2 to both sides. Here is the right-hand expression:

 `k * (k+1) * (2k+1) / 6 + (k+1)(k+1)`

Factor out (k+1)

 `(k+1) * [ k * (2k+1) / 6 + (k+1) ](k+1) * [ k * (2k+1) + 6k + 6 ] / 6(k+1) * [ 2k2 + 7k + 6 ] / 6`

The term in the brackets can be factored to give:

 `(k+2) * (2k+3)`

which can be rearranged to

 `[(k+1) + 1] * [2*(k+1) + 1]`

So we have, finally:

 `(k+1) * [(k+1) + 1] * [2*(k+1) + 1] / 6`

which is what we wanted to prove.

There is an even better proof in the link which uses a "telescoping sum."