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   1
4 5
9 14
16 30
25 55
36 91
49 140
64 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) / 6
n = 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."

No comments: