1. ## Bijective Proof

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.

2. ## Re: Bijective Proof

Originally Posted by myenemy
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
What is meant by bijective proof?

It seems that you want $\displaystyle \binom{n+1}{2}+\binom{n}{2}=n^2$ or $\displaystyle \frac{(n+1)!}{2!(n-1)!}+\frac{(n)!}{2!(n-2)!}=n^2$

3. ## Re: Bijective Proof

The number of squares above (or below) a diagonal in a square of size n is $\displaystyle \binom{n}{2}$.

4. ## Re: Bijective Proof

Here is a slightly different approach.

Consider the number of pairs (i, j) where $\displaystyle 1 \le i,j \le n$. There are $\displaystyle n^2$ of these.

Let's break the pairs into two sets: (1) those with $\displaystyle i < j$, and (2) those with $\displaystyle i \ge j$.

For (1), there are $\displaystyle \binom{n}{2}$ such pairs.

For (2), $\displaystyle i \ge j \iff j \le i \iff j < i+1 \iff j < k$ where $\displaystyle k = j+1$, so $\displaystyle 2 \le k \le n+1$.
If $\displaystyle j < k$ then there are no solutions with $\displaystyle j = n+1$ or $\displaystyle k = 1$; so the number of solutions is unchanged if we allow $\displaystyle 1 \le i \le n+1$ and $\displaystyle 1 \le k \le n+1$. So there are $\displaystyle \binom{n+1}{2}$ such pairs.

Comparing our results, we see $\displaystyle n^2 = \binom{n}{2} + \binom{n+1}{2}$.

I suppose I should add, since the problem statement asks for a bijective proof, that the bijection is between the set $\displaystyle n^2$ 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]

5. ## Re: Bijective Proof

a simple algebraic proof:

$\displaystyle \binom{n}{2} + \binom{n+1}{2}$

$\displaystyle =\frac{n!}{2!(n-2)!} + \frac{(n+1)!}{2!(n-1)!}$

$\displaystyle = \frac{(n-1)n}{2} + \frac{n(n+1)}{2}$

$\displaystyle = \frac{n^2 - n}{2} + \frac{n^2 + n}{2} = \frac{2n^2}{2} = n^2$