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 $\binom{n+1}{2}+\binom{n}{2}=n^2$ or $\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 $\binom{n}{2}$.

4. ## Re: Bijective Proof

Here is a slightly different approach.

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

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

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

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

Comparing our results, we see $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 $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:

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

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

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

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