Proof of the recurrence for Bell numbers by the block of the last element

Proof

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

1. Let $n$ be a natural number. Let $X = \set{1, \dots, n + 1}$, let $z = n + 1$, and let $Y = \set{1, \dots, n}$.
2. By the definition of the Bell numbers, $B_m$ is the number of partitions of an $m$-element set. So $B_{n+1}$ counts the partitions of $X$.
3. Let $P$ be a partition of $X$, and let $B$ be its block that contains $z$. Let $K = X \setminus B$. Then $K \subseteq Y$.
4. The other blocks $P \setminus \set{B}$ are nonempty, pairwise disjoint, and their union is $K$. So they form a partition of $K$.
5. Map $P$ to the pair $(K, P \setminus \set{B})$.
6. Conversely, let $K \subseteq Y$ and let $Q$ be a partition of $K$. The set $X \setminus K$ contains $z$, so it is nonempty. Then $Q \cup \set{X \setminus K}$ is a partition of $X$.
7. These two maps are inverse to each other. So the partitions of $X$ are in bijection with the pairs $(K, Q)$, where $K \subseteq Y$ and $Q$ is a partition of $K$.
8. For a fixed $K$ with $k$ elements, there are $B_k$ choices of $Q$.
9. By the number of $k$-element subsets, $Y$ has $\binom{n}{k}$ subsets $K$ with $k$ elements, for $0 \le k \le n$.
10. By the rule of sum, grouping the pairs by $k = |K|$, and by the bijection principle, $$B_{n+1} = \sum_{k=0}^{n} \binom{n}{k} B_k.$$