Recurrence for Stirling numbers of the first kind

Statement

Let $n$ and $k$ be natural numbers, and let $c(n, k)$ be the unsigned Stirling numbers of the first kind. Then $$c(n + 1, k + 1) = n\, c(n, k + 1) + c(n, k).$$

Remarks

Proof idea: look at the element $n + 1$ in a permutation of $n + 1$ elements. Either it is a fixed point, and the rest has $k$ cycles. Or it sits right after one of the $n$ other elements in its cycle. Example: $c(4, 2) = 3\, c(3, 2) + c(3, 1) = 3 \cdot 3 + 2 = 11$.

Explanations

L1 human

Insert a new element into a permutation written as cycles. It forms a new cycle of length $1$, or it goes into an existing cycle right after one of the $n$ old elements.