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.

  • 0
    Correct. It is what I meant to imply2012-02-21