Use a combinatoric proof to prove that:

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

I've had a couple of ideas on how to tackle this - first, I tried to see if I could divide m and n into two separate committee/groups of size m and n. But I wasn't able to figure out what the combination would represent. Then I tried to imagine whether it was equivalent to C(n,r) summed over m possibilities, but that doesn't seem correct either.

Any help?

  • $\begingroup$ Vandermonde identity. $\endgroup$ – Phicar Mar 28 '17 at 5:25
  • 3
    $\begingroup$ Possible duplicate of Combinatorial proof of summation of $\sum\limits_{k = 0}^n {n \choose k}^2= {2n \choose n}$ $\endgroup$ – mlc Mar 28 '17 at 5:29
  • $\begingroup$ Use $\binom{m}{k}= \binom{m}{m-k}$-- it makes the combinatorial interpretation easier. $\endgroup$ – Vik78 Mar 28 '17 at 5:35
  • $\begingroup$ On its face the proposed duplicate is a special case $m=n$ and $r=0$ of the present Question. I would sooner close that one (which has no Accepted Answer) as a duplicate of this one. $\endgroup$ – hardmath Mar 28 '17 at 16:30

Let we have set $S$ of $m+n$ elements and we need to choose $m+r$ of them. Let's separate $S$ to the two subsets $M$ of $m$ elements and $N$ of $n$ elements. Let we have $m-k$ elements chosen from $M$ (here $0 \le k \le m$) then we have $r+k$ elements chosen from $N$. Thus $$ {m+n \choose m+r} = \sum_{k=0}^m {m \choose m-k} {n \choose r+k} = \sum_{k=0}^m {m \choose k} {n \choose r+k}. $$

  • $\begingroup$ Aww shoot, C(m, k) = C(m, m - k). Then m-k + (r + k) = r + m...yes, it all makes sense now. $\endgroup$ – D. Sinatra Mar 28 '17 at 5:36

Think of $m+n$ as the cardinality of the union of two disjoint sets. For instance, suppose we are forming a committee of $m+r$ people from a set of $m$ men and $n$ women. In this context, what does the $k$ in the sum keep track of? What does ${m\choose k}{n\choose r+k}$ count?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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