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?
LikeLike
Shhhh 😛
Besides, any bijective proof beats any boring inductive argument xD
LikeLike
Bijections are awesome 😛
Your blog is so interesting
A Western Li
LikeLike