Proof of Vandermonde's identity by induction

Proof

We argue by induction on $n$. The claim for $n$ is that the identity holds for this $n$, every natural number $m$ and every natural number $r$.

1. Let $n = 0$. By the definition of the binomial coefficient, $\binom{0}{0} = 1$ and $\binom{0}{j} = 0$ for $j \ge 1$.
2. So in $\sum_{k=0}^{r} \binom{m}{k} \binom{0}{r-k}$ only the term $k = r$ is nonzero. The sum equals $\binom{m}{r} = \binom{m+0}{r}$.
3. Suppose the claim holds for $n$. Fix $m$ and $r$. We prove $\binom{m+n+1}{r} = \sum_{k=0}^{r} \binom{m}{k} \binom{n+1}{r-k}$.
4. If $r = 0$, both sides equal $1$, because $\binom{a}{0} = 1$ for every $a$.
5. Otherwise $r = s + 1$ for a natural number $s$. By Pascal's rule, $\binom{m+n+1}{s+1} = \binom{m+n}{s} + \binom{m+n}{s+1}$.
6. By the induction hypothesis for $n$, with $r = s$ and with $r = s + 1$, the left side is $L_1 + L_2$. Here $L_1 = \sum_{k=0}^{s} \binom{m}{k} \binom{n}{s-k}$ and $L_2 = \sum_{k=0}^{s+1} \binom{m}{k} \binom{n}{s+1-k}$.
7. In the right side $\sum_{k=0}^{s+1} \binom{m}{k} \binom{n+1}{s+1-k}$, the term $k = s + 1$ is $\binom{m}{s+1} \binom{n+1}{0} = \binom{m}{s+1} \binom{n}{0}$, since both coefficients $\binom{\cdot}{0}$ equal $1$.
8. For $k \le s$, write $s + 1 - k = (s - k) + 1$. Pascal's rule gives $\binom{n+1}{s+1-k} = \binom{n}{s-k} + \binom{n}{s+1-k}$.
9. So the right side equals $\sum_{k=0}^{s} \binom{m}{k} \binom{n}{s-k} + \sum_{k=0}^{s} \binom{m}{k} \binom{n}{s+1-k} + \binom{m}{s+1} \binom{n}{0}$.
10. The first sum is $L_1$. The last two parts together are $L_2$, whose term $k = s + 1$ is $\binom{m}{s+1} \binom{n}{0}$.
11. Hence the right side equals $L_1 + L_2$, which is the left side by step 6. This completes the induction.