Proof of the recurrence for Stirling numbers of the second kind

Proof

We sort the partitions by the block of the last element.

1. Let $n$ and $k$ be natural numbers. Let $X = \set{1, \dots, n + 1}$, let $z = n + 1$, and let $Y = \set{1, \dots, n}$.
2. By the definition of the Stirling numbers of the second kind, $S(n + 1, k + 1)$ is the number of partitions of $X$ into $k + 1$ blocks.
3. Let $P$ be such a partition, and let $B$ be its block that contains $z$. Either $B = \set{z}$, or $B$ has another element.
4. Case $B = \set{z}$. Then $P \setminus \set{B}$ is a partition of $Y$ into $k$ blocks.
5. Conversely, if $Q$ is a partition of $Y$ into $k$ blocks, then $Q \cup \set{\set{z}}$ is a partition of $X$ into $k + 1$ blocks. One of its blocks is $\set{z}$.
6. These maps are inverse to each other. So by the bijection principle, this case has $S(n, k)$ partitions.
7. Case $B \ne \set{z}$. Then $B \setminus \set{z}$ is nonempty. Replacing $B$ by $B \setminus \set{z}$ gives a partition $P'$ of $Y$ into $k + 1$ blocks.
8. Map $P$ to the pair $(P', B \setminus \set{z})$. The second entry is a block of $P'$.
9. Conversely, let $Q$ be a partition of $Y$ into $k + 1$ blocks, and let $C \in Q$. Replace $C$ by $C \cup \set{z}$. This gives a partition of $X$ into $k + 1$ blocks. In it, the block of $z$ is not $\set{z}$.
10. These maps are inverse to each other. So this case is in bijection with the pairs $(Q, C)$, where $Q$ is a partition of $Y$ into $k + 1$ blocks and $C \in Q$.
11. Each such $Q$ has exactly $k + 1$ choices of $C$. By the rule of sum over $Q$, there are $(k + 1)\, S(n, k + 1)$ such pairs.
12. The two cases are disjoint and cover all partitions of $X$ into $k + 1$ blocks. By the rule of sum, $$S(n + 1, k + 1) = (k + 1)\, S(n, k + 1) + S(n, k).$$