How to solve $\binom{n+m}{k} = \sum_{i=0}^{k} \binom{m}{i} \binom{n}{k-i} $

Question

How to prove this?

$n$, $m$ and $k \in \mathbb{N_{0}} $

$$\binom{n+m}{k} = \sum_{i=0}^{k} \binom{m}{i} \binom{n}{k-i}$$

Answer 1

Say you have $n+m$ numbered balls, where $n$ are red, and $m$ are blue. Then $\binom{n+m}{k}$ is the number of ways to choose $k$ balls regardless of colour, while $\binom{m}{i} \binom{n}{k-i}$ is the number of ways to choose $i$ blue balls and $k-i$ red ones from the same collection. Sum over all possible $i$, and you have the number of ways to pick $k$ balls regardless of colour. Thus the two expressions count the same thing, and must therefore be equal.