Tuesday 29 October 2013

combinatorics - Combinatorial identity using combinatorial argument: $left[sumlimits_{k=0}^{n} binom nkright] ^ 2 = sumlimits_{k=0}^{2n}binom{2n}k$



Is it possible to prove the following identity using combinatorial argument :




$$\left[\sum _{k=0}^{n} {n \choose k}\right] ^ 2 = \sum_{k=0}^{2n}{2n \choose k}$$


Answer



Suppose that you have a group of $n$ mixed couples. The lefthand side is the number of ways to choose a set of $k$ men and a set of $\ell$ women for some $k,\ell\in\{0,\dots,n\}$; the righthand side is the number of ways to choose an arbitrary subset of the group. Clearly these are the same.


No comments:

Post a Comment

real analysis - How to find $lim_{hrightarrow 0}frac{sin(ha)}{h}$

How to find $\lim_{h\rightarrow 0}\frac{\sin(ha)}{h}$ without lhopital rule? I know when I use lhopital I easy get $$ \lim_{h\rightarrow 0}...