# Prove $\sum_ {k=0} ^n {n \choose k}^2 = {2n \choose n}$? [duplicate]

Give a proof of the following identity using a double-counting argument:

$$\sum_ {k=0} ^r {m \choose k} {n \choose r - k} = {{m+n} \choose r}$$

Then using this result, derive the following special case from it.

$$\sum_ {k=0} ^n {n \choose k}^2 = {2n \choose n}$$ ?

For the first one, the method that I have is starting with the right hand side:

• Assume that k is a small number, which is less than r and m.
• We choose r from m + n can be divided into 2 parts:
• Choose k from m.
• Choose r - k from n.

My thinking is we can choose k from m and them choose r - k (because we only need to choose r) from n.

I'm stuck with the next part and not sure if my proof for the first part is right or not.

## marked as duplicate by Zain Patel, GNUSupporter 8964民主女神 地下教會, Lord Shark the Unknown, max_zorn, Lee David Chung LinMay 7 at 4:44

• Divide the $m+n$ objects into two groups, the first $m$ and the remaining $n$. Then you can choose $r$ objects from them by choosing $0$ from the first group and $r$ from the second, or $1$ from the first group and $r-1$ from the second, ... – logarithm May 7 at 0:42
• To prove the second put $m=n$ in the first. Then note that $\binom{n}{k}=\binom{n}{n-k}$. – logarithm May 7 at 0:43

If you want to reframe the first problem in such terms, think of it like this. Say we have $$m$$ men and $$n$$ women from which to pick a committee of $$r$$ members. Then on the one hand, we could pick $$r$$ from the entire group of $$m+n$$ people, thus getting $$C(m+n,r)$$ possible selections.
Alternatively, we could pick $$k$$ men then and $$r-k$$ women (note that these sum to $$r$$). Well, what values could $$k$$ be? We could be $$0$$ men, $$1$$ man, $$2$$ men, and so on, up to $$r$$ men. Thus, combining all this, we would get the summation on the left-hand side since you have to sum over the valid values of $$k$$ to account for each case.
As for the second one, just take $$n=r=m$$. The result should appear immediately. Don't forget the symmetry property of the binomial coefficient:
$$\binom n k = \binom{n}{n-k}$$