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 Lin May 7 at 4:44

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.

  • $\begingroup$ 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, ... $\endgroup$ – logarithm May 7 at 0:42
  • $\begingroup$ To prove the second put $m=n$ in the first. Then note that $\binom{n}{k}=\binom{n}{n-k}$. $\endgroup$ – logarithm May 7 at 0:43

Your overall idea for the first part is more or less right. Combinatorial arguments like this tend to flow more smoothly/logically if you think with a more concrete example. A popular idea seems to be committee selections.

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


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