# Counting two ways, $\sum \binom{n}{k} \binom{m}{n-k} = \binom{n+m}{n}$

prove by counting two ways:

I though to prove the right hand side I would say: Let n represent a number of boys and m a number of girls. We want to choose a group of n from boys and girls. But for the left hand side I want to keep the variables m and n girls and boys. But I don't know what k will be. Suggestions?

• Hint: replace $\binom nk$ by $\binom n{n-k}$. – Marc van Leeuwen Feb 15 '14 at 12:57
• $(1+x)^m(1+x)^n=(1+x)^{m+n}$ – Lucian Feb 15 '14 at 13:26

Suppose $n \leq m$.
Then if you want to choose $n$ people, you can choose $k$ boys in $\binom{n}{k}$ ways and $n-k$ girls in $\binom{m}{n-k}$ ways , for $k \in \{0,1, \dots n\}$.
So we have $$\sum_{k = 0}^{n} \binom{n}{k} \binom{m}{n-k} = \binom{n+m}{n}$$
If you are choosing $k$ girls, then exactly $k$ of the boys will not be chosen (since you are choosing as many children as there are boys).