# Stirling numbers of the second kind - proof

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\}$$

• Use the recurrence for the Stirling numbers. Oct 28 '18 at 16:41
• There are some basic proofs at the following MSE link. Oct 28 '18 at 17:32

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.