# Combinatorial Identity and Counting

Show that $\binom{2n}{2} = 2 \binom{n}{2}+n^2$.

LHS: This is the number of pairs of $2n$ distinct elements.

RHS: We can rewrite this as $2 \binom{n}{2}+ \binom{n}{1} \binom{n}{1}$. So you can divide up the $2n$ distinct elements into two subsets of $n$ elements. Then pick an element from each of these subsets to form a pair. Or you can just choose $2$ elements from the $n$ element subset (and multiply by $2$ since order matters).

Is this the correct idea?

• Your last note isn't quite right - but you're close. If you divide your set of $2n$ elements into 2 sets of $n$ elements, then there are three different ways of choosing 2 elements from your original set: they can both come from the first set (in $n\choose 2$ ways), they can both come from the second set (also in $n\choose 2$ ways), or one can come from each set (in $n\times n$ ways). Summing these gives the RHS of your formula. Now, can you see how this would generalize to the case of uneven splits? – Steven Stadnicki Dec 26 '10 at 0:21

Looks good to me. Also you could just work numerically: ${{2n} \choose 2}=\frac{1}{2} \times 2n(2n-1)=n(2n-1)=2n^2-n=n(n-1)+n^2=2{n \choose 2}+n^2$.
$2n \choose 2$ is the sum of numbers from $1$ to $2n-1$, which is the sum of even numbers from $2$ to $2(n-1)$, which is $2{n\choose 2}$, and odd numbers from $1$ to $2n-1$. The latter is of course $n^2$.