Theorem: Prove that for $k \leq m,n$, $\sum_{i=0}^{k}\binom{m}{i}\binom{n}{k-i} = \binom{m}{0}\binom{n}{k}+\binom{m}{1}\binom{n}{k-1}+\cdots+\binom{m}{k}\binom{n}{0}=\binom{m+n}{k}$ Proof: Let $A,B$ be sets such that $|A| = m$ and $|B| = n$ and $A \cap B = \emptyset$. Then, it is clear that for a fixed $k \leq n,m$, we have that $X := |\{S \subseteq A \cup B: |S| = k\}| = \sum_{i=0}^{k}\binom{m}{i}\binom{n}{k-i}$ because we can select the number $i$ of elements in $A$ that will contribute to $S$ and choose the rest of the remaining $k-i$ elements in $B$ (these multiply together by the multiplication principle and then we sum over all possible $i$ yielding the expression). On the other hand, $X = \binom{m+n}{k}$ because we know that $|A \cup B| = m+n$ and $\binom{m+n}{k}$ denotes the number of $k$-elements subsets we can form from a set (in this case $A \cup B$) of size $m+n$.