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 n

^{2}for n = 1 to n = k? The squares and the sum go like this:

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:

To find the sum of squares for k+1, we add (k+1)

^{2}to both sides. Here is the right-hand expression:

Factor out (k+1)

The term in the brackets can be factored to give:

which can be rearranged to

So we have, finally:

which is what we wanted to prove.

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

## No comments:

Post a Comment