If you were asked to find the sum of the first four cubes, you would easily be able to do so:

But here you may notice something interesting:

It turns out that this holds for the sum of the first cubes for any — an *identity*. This identity can be written also as:

A second way of expressing the same identity simplifies the right side and expresses it as a combination:

### A proof by bijection

This identity can be proven combinatorially by noticing that is the number of ways to choose 2 elements with repetition from the set {1..n} — the following is a proof by Benjamin and Orrison.

In this proof, we prove the third form of the identity

by constructing one set of size and constructing another set of size , then constructing a bijection between the two sets.

Let be the set of ordered 4-pairs such that — that is, the fourth integer of the pair is greater or equal to each of the other three. If we fix , the number of possibilities for the variables is . As ranges from 1 to n, the total number of elements in is equal to .

Also, since is the number of ways to choose 2 elements with repetition from the set {1..n}, there are pairs of integers satisfying . So let be the set of pairs of such pairs where and . The number of elements in is then .

We further partition the sets as follows: let be the subset of where and let be the subset of where . Similarly, let be the subset of where and let be the subset of where . We can construct a bijection between and by constructing two bijections:

The following is trivially a bijection from to — the case where :

The equivalent bijection from to — the case where :

We can confirm that the two operations we defined are indeed bijections. This proves the identity.

Would it not be easier to inductively prove that the sum of the first n integers is n(n+1)/2 and that the sum of the first n cubes is n^2(n+1)^2/4, which equals (n(n+1)/2)^2?

Shhhh :P

Besides, any bijective proof beats any boring inductive argument xD

Bijections are awesome :P

Your blog is so interesting

A Western Li