Theorem 1 ([1] 24.1.1 formula A. II.)   For any $p$ and $q$ and any $k$ with $0\le k\le p+q$ \begin{equation} \binom{p+q}{k}=\sum_{i=0}^k\binom{p}{i}\binom{q}{k-i}.\tag{*} \end{equation}

Proof. Let $P$ and $Q$ be disjoint sets with $|P|=p$ and $|Q|=q$ Then the left-hand side of Equation (*) is equal to the number of subsets of $P\cup Q$ of size $k$ To build a subset of $P\cup Q$ of size $k$ we first decide how many elements, say $i$ with $0\le i\le k$ we will select from $P$ We can then select those elements in $\binom{p}{i}$ ways. Once we have done so, we must select the remaining $k-i$ elements from $Q$ which we can do in $\binom{q}{k-i}$ ways. Thus there are $\binom{p}{i}\binom{q}{k-i}$ ways to select a subset of $P\cup Q$ of size $k$ subject to the restriction that exactly $i$ elements come from $P$ Summing over all possible $i$ completes the proof.