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:
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.
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."