2
$\begingroup$

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.

$\endgroup$

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
1
$\begingroup$

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

$\endgroup$

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