Stirling Numbers: Proof $S(n+1,m) = \sum_{k=0}^{n} {n \choose k}S(k,m-1)$ I'm not sure whether my attempt of proof is correct, mainly because of the choice with an object (which I called $a_{n+1}$) that I made.
Attempt:
Let place the object $a_{n+1}$ alone in a box. So let distribute the $n$ distinguishable objects into the remaining $m-1$ indistinguishable boxes.
Let pick $k$ out $n$ objects. This can be done in ${n \choose k}$ ways.
We can either put all $k-1$ objects first in the $m-1$ and then put the remaining $a_k$ object in one of them, which can be done in way $(m-1)S(k-1,m-1)$;
or we can distribute the first $k-1$ into $m-2$ boxes and put $a_n$ in the remaining box alone (a class of just one object). We have here ways $S(k-1, m-2)$.
By the rule of product in each case we have respectively
$${n \choose k}(m-1)S(k-1,m-1)$$
and
$${n \choose k}S(k-1, m-2)$$
And since $0 \leq k \leq n$, then by the rule of sum finally
\begin{align*}
S(n+1,m) &= \sum_{k=0}^{n} {n \choose k}(m-1)S(k-1,m-1) + {n \choose k}S(k-1, m-2)\\
&=\sum_{k=0}^{n} {n \choose k}\bigg[(m-1)S(k-1,m-1) + S(k-1, m-2)\bigg]\\
&=\sum_{k=0}^{n} {n \choose k}S(k,m-1)
\end{align*}

This doesn’t quite work, because you’ve counted only those partitions that have $a_{n+1}$ occupying a box by itself. Try this instead: choose $n-k$ of the other objects to go into the same box as $a_{n+1}$. There are $\binom{n}{n-k}=\binom{n}k$ ways to do this. Then you have $k$ objects remaining to distribute amongst the other $m-1$ boxes.
