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

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?

• Vandermonde identity. – Phicar Mar 28 '17 at 5:25
• – mlc Mar 28 '17 at 5:29
• Use $\binom{m}{k}= \binom{m}{m-k}$-- it makes the combinatorial interpretation easier. – Vik78 Mar 28 '17 at 5:35
• 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. – 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}.$$

• Aww shoot, C(m, k) = C(m, m - k). Then m-k + (r + k) = r + m...yes, it all makes sense now. – 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?