Algebraic derivation of the recurrence for Stirling numbers of the second kind

Question

Usually, the Stirling numbers of the second kind are defined as the number $S(n, k)$ of ways of partitioning a set of size $n$ into $k$ subsets. However, another way of defining them is as the coefficients $S(n, k)$ that satisfy the equations

$$x^n = \sum_{k = 0}^n S(n, k) x^{\underline{k}} \label{1}\tag{1}$$

where $x^{\underline{k}} = x (x - 1) \cdots (x - k + 1)$ is the falling factorial.

The Stirling numbers of the second kind also satisfy the recurrence relation

$$S(n + 1, k) = k S(n, k) + S(n, k - 1) \label{2}\tag{2}$$

It is straightforward to derive this recurrence when $S(n, k)$ is defined as the number of ways of partitioning a set of size $n$ into $k$ subsets. However, since \ref{1} characterizes the Stirling numbers of the second kind, it should be possible to derive it algebraically from \ref{1}.

How can the recurrence \ref{2} be derived algebraically from \ref{1}?

 

Motivation

The (unsigned) Stirling numbers of the first kind $\begin{bmatrix}n \\ k\end{bmatrix}$ can be defined as either the number of permutations on a set of $n$ elements that can be written as a product of $k$ disjoint cycles or as the coefficients that satisfy the equations

$$x^{\overline{n}} = \sum_{k = 0}^n \begin{bmatrix}n \\ k\end{bmatrix} x^k \label{3}\tag{3}$$

where $x^{\overline{n}} = x (x + 1) \cdots (x + n - 1)$ is the rising factorial.

Their recurrence relation

$$\begin{bmatrix}n + 1 \\ k\end{bmatrix} = n \begin{bmatrix}n \\ k\end{bmatrix} + \begin{bmatrix}n \\ k - 1\end{bmatrix} \label{4}\tag{4}$$

can derived either from their definition in terms of products of disjoint cycles or algebraically from \ref{3} by noting that $x^{\overline{n + 1}} = x \cdot x^{\overline{n}} + k \cdot x^{\overline{n}}$, using \ref{3} to substitute for $x^{\overline{n}}$ and equating coefficients.

Deriving the same recurrence for both definitions is one way of showing that the two definitions for unsigned Stirling numbers of the first kind are equivalent. An answer to my question above would explain how the same overall proof strategy can be used to show that the two definitions of Stirling numbers of the second kind are equivalent.

I know another way to prove that the two definitions are equivalent, but this would be more elegant and I would also like to know how it can be done.

Answer 1

We have \begin{eqnarray*} x^{n+1}=\sum_{k=1}^{n+1} S(n+1,k) x^{\underline{k}}. \end{eqnarray*} Note $x \times x^{\underline{k}} =x^{\underline{k+1}}+k x^{\underline{k}}$, so \begin{eqnarray*} x^{n+1}=x\times x^n &=& x \sum_{k=1}^{n} S(n,k) x^{\underline{k}} \\ &=&\sum_{k=1}^{n} S(n,k) x^{\underline{k+1}}+ k \sum_{k=1}^{n} S(n,k) x^{\underline{k}} \\ &=& \sum_{k=2}^{n+1} S(n,k-1) x^{\underline{k}}+ \sum_{k=1}^{n} k S(n,k) x^{\underline{k}} \\ &=& \sum_{k=1}^{n+1} \left( \color{red}{S(n,k-1) + k S(n,k)} \right) x^{\underline{k}} \\ &=& \sum_{k=1}^{n+1} \color{red}{S(n+1,k)} x^{\underline{k}}. \end{eqnarray*}