Monday, January 21, 2008

Proof that the sum of the squares of the first n whole numbers is n^3/3 + n^2/2 + n/6

A recent thread on Hacker News that I started with a flippant comment turned into a little mathematical puzzle.

What's the sum of the square of the first n whole numbers?

It's well known that the sum of the first n whole numbers is n(n+1)/2. But what's the value of sum(i=1..n) n^2? (I'll call this number S for the remainder of this post).

It turns out that it's easy to prove that S = n^3/3 + n^2/2 + n/6 by induction. But how is the formula derived? To help with reasoning here's a little picture of the first 4 squares stacked up one on top of the other:



If we fill in the blank squares to make a rectangle we have the basis of a derivation of the formula:



Looking at the formerly blank squares (that I've numbered to assist with the thinking) we can see that the columns have 1 then 1+2 then 1+2+3 and finally 1+2+3+4 squares. Thus the columns are sums of consecutive whole numbers (for which we already have the n(n+1)/2 formula.

Now the total rectangle is n+1 squares wide (in this case 5) and its height is the final sum of whole numbers up to n or n(n+1)/2 (in the image it's 4 x 5 / 2 = 10. So the total number of squares in the rectangle is (n+1)n(n+1)/2 (in the example that's 5 x 10 = 50).

So we can calculate S as the total rectangle minus the formerly blank squares which gives:

S = (n+1)n(n+1)/2 - sum(i=1..n)sum(j=1..i) j
= (n(n+1)^2)/2 - sum(i=1..n) i(i+1)/2
2S = n(n+1)^2 - sum(i=1..n) i(i+1)
= n(n+1)^2 - sum(i=1..n) i^2 - sum(i=1..n) i
= n(n+1)^2 - S - n(n+1)/2
3S = n(n+1)^2 - n(n+1)/2
= n(n+1)( n+1 - 1/2 )
= n(n+1)(n+1/2)
= (n^2+n)(n+1/2)
= n^3 + n^2/2 + n^2 + n/2
= n^3 + 3n^2/2 + n/2
S = n^3/3 + n^2/2 + n/6

Labels:

0 Comments:

Post a Comment

Links to this post:

Create a Link

<< Home