Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
2  
see here for example. –  t.b. Mar 31 '12 at 11:18
add comment

marked as duplicate by Aryabhata, t.b., Kannappan Sampath, Dylan Moreland, Asaf Karagila Mar 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.

2 Answers

up vote 4 down vote accepted

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.

share|improve this answer
    
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
add comment

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

share|improve this answer
add comment

Not the answer you're looking for? Browse other questions tagged or ask your own question.