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.

Prove the following by way of a counting argument:

$$\binom{n}{0}^2+\binom{n}{1}^2+\cdots+\binom{n}{n}^2=\binom{2n}{n}$$

share|improve this question
    
Is this is a homework? What did you try? Where did you fail? –  user2468 Feb 21 '12 at 18:49
1  
Why not accepting some answers? You acceptance rate is "0%"! –  Gigili Feb 24 '12 at 13:30

1 Answer 1

Suppose you have $2n$ items. Break them into two equal groups of size $n$; fix an integer $k$, $0\le k \le n$.

Take $k$ from the first group and $n-k$ from the second. There are $${n\choose k}{n\choose n - k} = {n\choose k}^2$$ ways to do this.

Now if you take a sample of size $n$ from the $2n$, for a unique $k$ you will take $k$ from the first group and $n-k$ from the second. Sum over all $k$ and you get the result.

share|improve this answer
3  
A way to visualize this proof is to have an $n \times n$ grid, and count the number of ways (going either right or up) to get from the bottom left corner to the top right corner. If for each point of the main diagonal (going topleft-bottomright) you count the number of way to get to it from the bottom left vertex, and then multiply that by number of ways to get to the top right, you get this exact identity. –  Aryabhata Feb 21 '12 at 1:17
    
That's quite cool, Aryabhata. –  ncmathsadist Feb 21 '12 at 1:20
    
I am not sure what you mean by sum all k and get the result. Do you mind to explain some more? –  user25329 Feb 21 '12 at 1:26
1  
He guess he means $$\sum_{k=0}^n{n \choose k}{n\choose n-k}=\sum_{k=0}^n{n \choose k}^2$$ –  Pedro Tamaroff Feb 21 '12 at 1:42
    
I guess he means –  Pedro Tamaroff Feb 21 '12 at 1:52

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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