Theorem 1.7

#Theorem

Let $m, n$ and $r$ be non-negative integers with $r \leq m, n$ . Then
$(\binom{m + n}{r}) = \sum_{k = 0}^{r} (\binom{m}{r - k}) (\binom{n}{k})$

Proof:

Suppose there are $m$ items in one set and $n$ (different) items in a second set
Then the total number of ways to pick $r$ related elements from the union of these sets is $(\binom{m + n}{r})$
Another way to pick $r$ elements from the union is to pick $k$ elements from the first set and then $r - k$ elements from the second set, where $k$ is an integer with $0 \leq k \leq r$
This can be done in $(\binom{m}{k}) (\binom{n}{r - k})$ ways, using the product rule, and so the total is $\sum_{k = 0}^{r} (\binom{m}{k}) (\binom{n}{r - k})$
Therefore, $(\binom{m + n}{r}) = \sum_{k = 0}^{r} (\binom{m}{r - k}) (\binom{n}{k})$