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\}$ 
 A: 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.
