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

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?

Solution 1:

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