3
$\begingroup$

Possible Duplicate:
Proof that $\binom{n}{\smash{0}}^2+\binom{n}{1}^2+\cdots+\binom{n}{n}^2=\binom{\smash{2}n}{n}$ using a counting argument

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.

  • 2
    see [here](http://math.stackexchange.com/q/91457) for example. – 2012-03-31

2 Answers 2

5

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.

  • 0
    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. – 2012-03-31
2

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}$