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:

1^{3}+ ... + n^{3}= (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:

1^{3}= 1 = 1^{2}

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

1^{3}+ ... + k^{3}= (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)

^{2}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 = k^{2}+ 1 + 2k

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

(1 + ... + k)^{2}+ (k + 1)(k^{2}+ 1 + 2k) =

= (1 + ... + k)^{2}+ (k + 1)(k + 1)^{2}=

= (1 + ... + k)^{2}+ (k + 1)^{3}

But

(1 + ... + k)^{2}= 1^{3}+ ... + k^{3}

according to the hypothesis, so

(1 + ... + k)^{2}+ (k + 1)^{3}= 1^{3}+ ... + k^{3}+ (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.

## No comments:

Post a Comment