I was told that this equality can be derived easily using exponential generation functions:
\begin{equation*}
\begin{Bmatrix}
n\\ k
\end{Bmatrix}
=\frac{1}{k!}\sum\limits_{i \in [0,k]}(-1)^{k-i}\binom{k}{i}i^n
\end{equation*}
And I would like to know, how to start the proof in similar cases. Please, give me just a little hint.
Best Answer
The exponential generating function for the Stirling numbers of the secod kind is given by \begin{eqnarray*} \sum_{n=0}^{\infty} \sum_{k=0}^{n} \begin{Bmatrix}n\\ k \end{Bmatrix} \frac{x^n}{n!} y^k = \operatorname{exp}(y(e^x-1)). \end{eqnarray*} So \begin{eqnarray*} \frac{1}{n!} \begin{Bmatrix}n\\ k \end{Bmatrix} &=& [x^n] [y^k]: \operatorname{exp}(y(e^x-1)) \\ &=& [x^n] : \frac{(e^x-1)^k}{k!} \\ &=& [x^n] : \frac{1}{k!} \sum_{i=0}^{k} (-1)^{k-i} \binom{k}{i} e^{ix} \\ &=& \frac{1}{k!} \sum_{i=0}^{k} (-1)^{k-i} \binom{k}{i} \frac{i^n}{n!}. \\ \end{eqnarray*}