Geeky fact of the day, proven

A few weeks back, my colleague Patrik Fredriksson turned my attention to a "Geeky fact of the day" tweet by Josh Bloch by verifying Josh's claim for a small number of integers using Clojure. Having recently picked up a discrete mathematics book in an attempt to refresh my academic skills, I found an exercise that wanted you to prove exactly that, so I gave it a shot.

Clojure is great, no doubt about that, but mathematics also has its strong points: it's very stable, tool support is great and it scales tremendously well :-)

So, we want to prove that the sum of the n first cubes is equal to the sum of the first n positive integers squared:

13 + ... + n3 = (1 + ... + n)2

I'm going to use the principle of induction, which means that you start out with a concrete, simple case and show that the theorem holds for that. Then you assume that it's true for some arbitrary value k and show that the theorem then holds for k + 1. By virtue of a domino effect from your base case, the theorem is proven for all natural numbers.

Let's start with the induction basis:

13 = 1 = 12

So, it's obviously true for n = 1. Now for the induction hypothesis - assume that the theorem holds for n = k:

13 + ... + k3 = (1 + ... + k)2

Let's take a look at the right hand side expression evaluated for k + 1:

  ((1 + ... + k) + (k + 1))2 =
= (1 + ... + k)2 + (k + 1)2 + 2(k + 1)(1 + ... + k) =
= (1 + ... + k)2 + (k + 1)((k + 1) + 2(1 + ... + k))

I'm using the familiar expansion of (a + b)² and then factoring out (k + 1) from the last two terms. Focusing for a moment on the factor in bold:

  ((k + 1) + 2(1 + ... + k)) =
= ((k + 1) + 2(1 + ... + k - 1) + 2k) =
= (k + 2(1 + ... + k - 1) + 1 + 2k)

Narrowing in on the second term in this expression, we can use a clever trick:

  2(1 + ... + k - 1) =

=   1   +   2   + ... + k - 1 +
+ k - 1 + k - 2 + ... +   1   =

= (k - 1 + 1) + (k - 2 + 2) + ... + (1 + k - 1)

Using this symmetry we can deduct that

2(1 + ... + k - 1) = k(k - 1)

since there are k - 1 expressions each evaluating to k in the summation table above. Injecting this back we have

k + k(k - 1) + 1 + 2k = k2 + 1 + 2k

And this in turn back into the full right hand side expression:

  (1 + ... + k)2 + (k + 1)(k2 + 1 + 2k) =
= (1 + ... + k)2 + (k + 1)(k + 1)2 =
= (1 + ... + k)2 + (k + 1)3

But

(1 + ... + k)2 = 13 + ... + k3

according to the hypothesis, so

(1 + ... + k)2 + (k + 1)3 = 13 + ... + k3 + (k + 1)3

which is the left hand side of the original expression, for k + 1. This means that the induction hypothesis holds, and the theorem is proven.

Q.E.D.