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\}$
Stirling numbers of the second kind – proof 2
combinatoricsfactorialgenerating-functionsstirling-numbers
Related Solutions
Yes, this equation has a combinatorial interpretation.
The number $\left\{k\atop n\right\}$ counts the number of partitions of the linearly ordered set $\mathbf k=\{1, \dots, k\}$ into $n$ nonempty subsets. Let us see how one can think of such a partition. Below, you can see a partition of $\mathbf{15}$ into $4$ nonempty subsets (the linear order goes from left to right).
The data of this partition is equivalent to the following data:
Here, a vertical line was inserted just before a new color is encountered when going from left to right. The colors were ordered by their order of occurence:
$$\text{Red}<\text{Blue}<\text{Green}<\text{Pink}$$
and were assigned the numbers $0,1,2,3$ respectively. Now, remark that the data of the above decomposition is also equivalent to the data of the diagram
because the obscured numbers are just $0,1,2,3$ in order of occurence. The initial partition can be completely reconstructed from this last diagram. I'll leave it up to you to check that this decomposition yields the claimed identity of power series.
Since $s + 1 \leq i \leq n$, we see that $i>s \, \, \, \forall s < n$. Hence $\binom{s}{i}=0$. But each term of your sum is the product of $\binom{s}{i}$ and other values, which means each term will be zero. So the entire sum will be zero.
Best Answer
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!}.$$