Stirling numbers of the second kind – proof

Question

For a fixed integer k, how would I prove that

$$\sum_{n\ge k} \left\{n \atop k\right\}x^n= \frac{x^k}{(1-x)(1-2x)…(1-kx)}.$$

where $\left\{n \atop k\right\}=k\left\{n-1 \atop k\right\}+\left\{n-1 \atop k-1 \right\}$

Answer 1

The definition of ${n\brace k}$ through the recursion is easily seen to be equivalent to the combinatorial definition "the number of ways for partitioning a set with $n$ elements into $k$ non-empty subsets". $m^n$ can be interpreted as the number of functions from $[1,n]$ to $[1,m]$: if we classify them according to the cardinality of their range, we may easily check that $$ m^n =\sum_{k=1}^{n}{n\brace k}k! \binom{m}{k} \tag{1}$$ i.e. Stirling numbers of the second kind allow to decompose monomials into linear combination of binomial coefficients. In equivalent terms ${n\brace k}k!$ is the number of surjective functions from $[1,n]$ to $[1,k]$, and $${n \brace k}k!=\sum_{j=0}^{k}\binom{k}{j}j^n (-1)^{k-j} \tag{2}$$ follows by inclusion-exclusion. $(2)$ is a natural counter-part of $(1)$, and it leads to $$ {n\brace k} x^n = \sum_{j=0}^{k}\frac{x^n j^n (-1)^{k-j}}{j!(k-j)!} \tag{3}$$ then to: $$ \sum_{n\geq k}{n\brace k}x^n = x^k\sum_{j=0}^{k}\frac{j^k (-1)^{k-j}}{j!(k-j)!(1-jx)}=x^k\sum_{j=1}^{k}\frac{j^k}{k!}\binom{k}{j}\frac{(-1)^{k-j}}{1-jx}.\tag{4}$$ By residues or equivalent techniques, the last sum can be easily checked to be the partial fraction decomposition of $\frac{1}{(1-x)(1-2x)\cdot\ldots\cdot(1-kx)}$, proving the claim.