[proofplan]
We count the same finite set in two ways. First, we count all $n$-element subsets of a set with $r+s$ elements, giving $\binom{r+s}{n}$. Second, we split the underlying set into two disjoint parts of sizes $r$ and $s$, then count an $n$-element subset according to how many elements it takes from the first part. Summing over that number gives the left-hand side.
[/proofplan]
[step:Choose a disjoint union with prescribed sizes]
Define
\begin{align*}
A = \{i \in \mathbb{N} : 1 \leq i \leq r\}
\end{align*}
and
\begin{align*}
B = \{r+j \in \mathbb{N} : j \in \mathbb{N}, 1 \leq j \leq s\}.
\end{align*}
Then $A$ and $B$ are disjoint finite sets with $|A|=r$ and $|B|=s$. Let $U := A \cup B$. Since $A \cap B=\varnothing$, we have $|U|=r+s$.
[/step]
[step:Count all $n$-element subsets at once]
Let
\begin{align*}
\mathcal{C} = \{T \subset U : |T|=n\}
\end{align*}
be the set of all $n$-element subsets of $U$. By the definition of the [binomial coefficient](/page/Binomial%20Coefficient) as the number of subsets of a finite set of a given size, and with the zero convention when $n>|U|$, we have
\begin{align*}
|\mathcal{C}| = \binom{r+s}{n}.
\end{align*}
[/step]
[step:Partition the subsets by how many elements they take from $A$]
For each $k \in \{0,1,\dots,n\}$, define
\begin{align*}
\mathcal{C}_k = \{T \in \mathcal{C} : |T \cap A|=k\}.
\end{align*}
The sets $\mathcal{C}_0,\mathcal{C}_1,\dots,\mathcal{C}_n$ are pairwise disjoint, and their union is $\mathcal{C}$, because every $T \in \mathcal{C}$ has a unique integer $k=|T \cap A|$ between $0$ and $n$. Therefore
\begin{align*}
|\mathcal{C}| = \sum_{k=0}^{n} |\mathcal{C}_k|.
\end{align*}
[guided]
We now refine the count by recording one statistic of a subset: how many of its elements lie in the first block $A$. For each $k \in \{0,1,\dots,n\}$, define
\begin{align*}
\mathcal{C}_k = \{T \in \mathcal{C} : |T \cap A|=k\}.
\end{align*}
This definition is meaningful because every $T \in \mathcal{C}$ is a finite subset of $U$, and hence $T \cap A$ is a finite subset of $A$.
The family $\mathcal{C}_0,\mathcal{C}_1,\dots,\mathcal{C}_n$ is pairwise disjoint. Indeed, if $T \in \mathcal{C}_k \cap \mathcal{C}_\ell$, then $|T \cap A|=k$ and $|T \cap A|=\ell$, so $k=\ell$. Their union is all of $\mathcal{C}$, because each $T \in \mathcal{C}$ has exactly $n$ elements, so the integer $|T \cap A|$ lies between $0$ and $n$ and places $T$ into exactly one of the classes $\mathcal{C}_k$.
Thus the addition rule for finite disjoint unions gives
\begin{align*}
|\mathcal{C}| = \sum_{k=0}^{n} |\mathcal{C}_k|.
\end{align*}
This is the point where the sum over $k$ in Vandermonde's identity appears: the index $k$ records the number of chosen elements coming from the first set $A$.
[/guided]
[/step]
[step:Count each partition class by choosing from $A$ and from $B$]
Fix $k \in \{0,1,\dots,n\}$. Define
\begin{align*}
\mathcal{A}_k = \{P \subset A : |P|=k\}
\end{align*}
and
\begin{align*}
\mathcal{B}_{n-k} = \{Q \subset B : |Q|=n-k\}.
\end{align*}
Define a map
\begin{align*}
\Phi_k: \mathcal{C}_k \to \mathcal{A}_k \times \mathcal{B}_{n-k}, \qquad T \mapsto (T \cap A, T \cap B).
\end{align*}
This map is bijective, with inverse
\begin{align*}
\Psi_k: \mathcal{A}_k \times \mathcal{B}_{n-k} \to \mathcal{C}_k, \qquad (P,Q) \mapsto P \cup Q.
\end{align*}
Indeed, since $A$ and $B$ are disjoint and $U=A \cup B$, every subset $T \subset U$ decomposes uniquely as
\begin{align*}
T = (T \cap A) \cup (T \cap B).
\end{align*}
Hence
\begin{align*}
|\mathcal{C}_k| = |\mathcal{A}_k|\,|\mathcal{B}_{n-k}| = \binom{r}{k}\binom{s}{n-k}.
\end{align*}
The same formula remains valid when $k>r$ or $n-k>s$, because then the corresponding family of subsets is empty and the corresponding binomial coefficient is $0$ by convention.
[/step]
[step:Equate the two counts]
Combining the partition count with the count of each partition class gives
\begin{align*}
|\mathcal{C}| = \sum_{k=0}^{n} \binom{r}{k}\binom{s}{n-k}.
\end{align*}
The direct count gave
\begin{align*}
|\mathcal{C}| = \binom{r+s}{n}.
\end{align*}
Equating these two expressions for the same finite cardinality $|\mathcal{C}|$ yields
\begin{align*}
\sum_{k=0}^{n} \binom{r}{k}\binom{s}{n-k} = \binom{r+s}{n}.
\end{align*}
This proves the identity.
[/step]
