I have been given a problem to prove the following by a bijective proof. Im not even sure where to start on the bijection if any help can be given that would be great!!
the identity is:
(n choose 2) + ((n+1) choose 2) = n^2
Sorry i dont know how to display the message so that it looks mathematicaly correct.
Here is a slightly different approach.
Consider the number of pairs (i, j) where . There are of these.
Let's break the pairs into two sets: (1) those with , and (2) those with .
For (1), there are such pairs.
For (2), where , so .
If then there are no solutions with or ; so the number of solutions is unchanged if we allow and . So there are such pairs.
Comparing our results, we see .
[edit]I suppose I should add, since the problem statement asks for a bijective proof, that the bijection is between the set pairs (i,j) and the union of the sets given in (1) and (2). I am assuming that what is called a "bijective" proof is the same as what is often called a "combinatoric" proof. [/edit]