Stirling numbers of the second kind - proof 2 For a fixed integer $k$, how would I prove that 
$\sum_{n\ge k} \left\{n \atop k \right\} \frac{x^n}{n!}=\frac{1}{k!}(e^x -1)^k $
where $\left\{n \atop k\right\} = k\left\{n-1 \atop k\right\}+\left\{n-1 \atop k-1\right\}$
 A: In proving
$$\sum_{n\ge k} {n\brace k} \frac{z^n}{n!}
= \frac{(\exp(z)-1)^k}{k!}$$
we use induction. We get for $k=1$
$$\sum_{n\ge 1} {n\brace 1} \frac{z^n}{n!}
= \sum_{n\ge 1} \frac{z^n}{n!}
= \frac{(\exp(z)-1)^1}{1!}$$
and the base case holds. For the induction step we have
supposing it holds for $k$
$$\frac{\exp(z)-1}{k+1}
\sum_{n\ge k} {n\brace k} \frac{z^n}{n!}
= \frac{(\exp(z)-1)^{k+1}}{(k+1)!}.$$
Note however that for $m\ge k+1$ we get (power series starts
at $z^{k+1}$)
$$[z^m] \frac{\exp(z)-1}{k+1}
\sum_{n\ge k} {n\brace k} \frac{z^n}{n!}
= \sum_{q=k}^{m-1} {q\brace k} \frac{1}{q!}
[z^{m-q}] \frac{\exp(z)-1}{k+1}
\\ = \frac{1}{m!} \times  \frac{1}{k+1}
\sum_{q=k}^{m-1} {m\choose m-q} {q\brace k}.$$
Next observe that
$$\sum_{q=k}^{m-1} {m\choose m-q} {q\brace k}
= (k+1) {m\brace k+1}$$
because the LHS  counts marked set partitions of $m$  into $k+1$ sets:
we first choose  $m-q$ elements of $[m]$ that go  into the set bearing
the marker,  and partition the rest  into $k$ sets. Clearly  we obtain
every  partition of  $m$ into  $k+1$  sets (RHS)  exactly $k+1$  times
(available  choices  for  the  marker). This  concludes  the  argument
by induction because we have shown that
$$\frac{(\exp(z)-1)^{k+1}}{(k+1)!}
= \sum_{m\ge k+1} {m\brace k+1} \frac{z^m}{m!}.$$
