4
$\begingroup$

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

  • 0
    Is this is a homework? What did you try? Where did you fail?2012-02-21

1 Answers 1

11

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.

  • 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.2012-02-21
  • 0
    That's quite cool, Aryabhata.2012-02-21
  • 0
    I am not sure what you mean by sum all k and get the result. Do you mind to explain some more?2012-02-21
  • 2
    He guess he means $$\sum_{k=0}^n{n \choose k}{n\choose n-k}=\sum_{k=0}^n{n \choose k}^2$$2012-02-21
  • 0
    *I guess he means*2012-02-21
  • 0
    Correct. It is what I meant to imply2012-02-21