There have been a number of proofs for this, such as:
How to prove Vandermonde's Identity: $\sum_{k=0}^{n}\binom{R}{k}\binom{M}{n-k}=\binom{R+M}{n}$?, and
Vandermonde's Identity: How to find a closed formula for the given summation.
However, they involve a lot of hand-waving or "consider a K-by-K matrix.. or "Suppose a committee consists of m men and n women".
I'm looking for a good solid step-by-step proof:
The best one I've found comes from this's Algebraic Proof:
where in line 1, the binomial theorem is applied.
From lines 1 to 2, it's just a factoring of exponents.
From line 2 to 3, it's an application of the binomial theorem on each factor term.
From line 3 to 4 however, I'm looking for some missing (assumed obvious) steps. They'll probably be a set of change of variables such as $\textrm{let } j=r-i$ then a new equation, then maybe another change of variables.
Can someone please provide step-by-step equations from line 3 to line 4?
Best Answer
Simple rearranging gives \begin{equation}\begin{aligned} \sum_{i=0}^m\begin{pmatrix}m\\i\end{pmatrix}x^i\sum_{j=0}^n\begin{pmatrix}n\\j\end{pmatrix}x^j&=\sum_{i=0}^m\sum_{j=0}^n\begin{pmatrix}m\\i\end{pmatrix}\begin{pmatrix}n\\j\end{pmatrix}x^{i+j}. \end{aligned}\end{equation} The trick is to then swap the sum over $i$ and $j$ for a sum over $r=i+j$ and $i$. \begin{equation}\begin{aligned} \sum_{i=0}^m\begin{pmatrix}m\\i\end{pmatrix}x^i\sum_{j=0}^n\begin{pmatrix}n\\j\end{pmatrix}x^j&=\sum_{r=0}^{m+n}\,\sum_{i=0}^{\min(m, r)}\begin{pmatrix}m\\i\end{pmatrix}\begin{pmatrix}n\\r-i\end{pmatrix}x^{r}. \end{aligned}\end{equation} Finally, we use that $\begin{pmatrix}a\\b\end{pmatrix} = 0$ for $b>a$ to extend the sum over $i$ from $\min(m, r)$ to $r$. \begin{equation}\begin{aligned} \sum_{i=0}^m\begin{pmatrix}m\\i\end{pmatrix}x^i\sum_{j=0}^n\begin{pmatrix}n\\j\end{pmatrix}x^j&=\sum_{r=0}^{m+n}\,\sum_{i=0}^r\begin{pmatrix}m\\i\end{pmatrix}\begin{pmatrix}n\\r-i\end{pmatrix}x^{r}. \end{aligned}\end{equation}