I need help satisfying this recurrence. Thanks in advance!
Show that the Stirling numbers of the second kind satisfy the recurrence:
$$ S(k,n) = \sum_{i=1}^k S(k-i, n-1) {k-1 \choose i-1} $$
I think a partition of $[k]$ into n blocks has a block containing $k$. So then, if this block has size $i$, when you remove it, you get a partition of a set of size $k−i$ into $n−1$ blocks. The number of possible sets of size $i$ containing $k$ is ${k-1 \choose i-1}$ and $i$ can be any number between 1 and $k$. Each partition of $k$ into $n$ blocks may be constructed exactly once by first choosing the block containing k and then partitioning the remaining elements into $n − 1$ blocks.
I'm not sure if I am thinking about this the right way, but any help would be greatly appreciated.