# How to prove it by means of a combinatorial argument?(A combinatorial exercise) [duplicate]

It is an exercise in a book on discrete mathematics.It is like this.

Give a combinatorial argument to prove that $\sum_{k=0}^{n}C\left ( n,k \right)^{2}=C\left ( 2n,n \right )$.

I don't know how to begin with it.It's hard for me to construct such a set,or the context.I learned it by myself and no one around can help me whit my answer. Thanks for your help.

-

## marked as duplicate by Aryabhata, t.b., Kannappan Sampath, Dylan Moreland, Asaf KaragilaMar 31 '12 at 18:02

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

see here for example. – t.b. Mar 31 '12 at 11:18

## 2 Answers

Consider the right hand side of the equality. What does it tell you? Translated to english the RHS is "the number of n-subsets of a 2n-set" (where by n-set I mean a set of cardinality n). Now consider the $2n$-set. Split it up in two sets of equal size $n$. You can pick a n-set by choosing $n$ elements from one of the sets and zero from the other, or choosing $n-1$ elements from one of the n-sets and $1$ element from the other and so on. I.e. $$C(2n,n)=\sum{C(n,k)C(n,n-k)=\sum{C(n,k)^2}}$$ The last equality follows since the number of ways of choosing $k$ elements from a $n$ set is the same number of ways as choosing those $n-k$ elements that shall not belong to a $k$-subset.

-
Yes,at first I just can't catch that C(n,k)2 is just C(n,k)C(n,n−k).And I was stuck in it. – tamlok Mar 31 '12 at 12:37

Use the Chu-Vandermonde identity, as recommended by t.b.: $${m+n \choose r}=\sum_{k=0}^r{m \choose k}{n \choose r-k},\qquad m,n,r\in\mathbb{N}_0,$$ and set $m=n$, $r=n$ and use ${n \choose n-k}={n \choose k}$ to get: $$\sum_{k=0}^n{n \choose k}^2= {2n \choose n}$$

-