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