Сombinatorial proof for recurrent formula of stirling's numbers

Question

What would be combinatorial proof for this formula:

$$S(n,k) = \sum_{i=1}^{n}S(n-i, k-1)k^{i-1}$$

where $n \geq k$

Answer 1

HINT: For each partition $\pi=\{P_1,\ldots,P_k\}$ of $[n]$ into $k$ parts let $i_\pi$ be minimal such that $P_j\cap[n-i_\pi]=\varnothing$ for some $i\in[k]$. For a fixed $i$, how many partitions $\pi$ are there such that $i_\pi=i$?