Formula involving the Stirling numbers of the second kind

Question

I was studying chapter 4 of the book "Generatingfunctionology" by Herbert S.Wilf when I got stuck in the proof of the following equality, $$ \sum_{k=1}^{n} \Big\{ \begin{matrix} n \\ k \end{matrix} \Big\}\cdot y^{k}=e^{-y}\cdot \sum_{r\geq 1}\dfrac{r^{n}}{r!}y^{r}, $$ where $\Big\{ \begin{matrix} n \\ k \end{matrix} \Big\}$ is a Stirling number of the second kind. I have arrived to prove the following equality, $$ \sum_{r=0}^{k} \binom{k}{r}\cdot(k-r)^{n}\cdot (x-1)^{r}= k!\cdot \sum_{t=0}^{k} \Big\{ \begin{matrix} n \\ k-t\end{matrix}\Big\}\cdot\dfrac{x^{t}}{t!}. $$ What change of variable has been made? According to the author, he just used the formula for the product of exponential generating functions, $$ c_{k}=\sum_{t=0}^{k}\binom{k}{t}\cdot a_{k-t}\cdot b_{t}. $$

Answer 1

Let's go from the RHS: one has \begin{align*} e^{-y}\sum_{r= 1}^{+\infty}\dfrac{r^{n}}{r!}y^{r} & = \left(\sum_{r=0}^{+\infty} \dfrac{(-y)^r}{r!}\right) \times \left(\sum_{r= 1}^{+\infty}\dfrac{r^{n}}{r!}y^{r} \right) \\ & = \sum_{r=0}^{+\infty} \left( \sum_{k=0}^r \dfrac{(-y)^{r-k}}{(r-k)!} \times\dfrac{k^n y^k}{k!}\right) \\ & = \sum_{r=0}^{+\infty} \dfrac{1}{r!}\left( \sum_{k=0}^r (-1)^{r-k}{r \choose k}k^n\right) y^r \\ \end{align*}

But by definition (or by the well-known explicit formula), one has $$\dfrac{1}{r!}\left( \sum_{k=0}^r (-1)^{r-k}{r \choose k}k^n\right) = \Big\{ \begin{matrix} n \\ r \end{matrix} \Big\}$$

so you get $$e^{-y}\sum_{r= 1}^{+\infty}\dfrac{r^{n}}{r!}y^{r} = \sum_{r=0}^{+\infty} \Big\{ \begin{matrix} n \\ r \end{matrix} \Big\} y^r $$

Since $ \Big\{ \begin{matrix} n \\ r \end{matrix} \Big\} = 0 $ as soon as $r \geq n$, this reduces finally to the given formula $$\boxed{e^{-y}\sum_{r= 1}^{+\infty}\dfrac{r^{n}}{r!}y^{r} = \sum_{r=0}^{n} \Big\{ \begin{matrix} n \\ r \end{matrix} \Big\} y^r }$$

Answer 2

By definition, $$ r^n = \sum\limits_{k=0}^n \left\{\begin{matrix} n \\ k\end{matrix}\right\} (r)_k. $$ Expanding $(r)_k = \frac{r!}{(r-k)!}$ and dividing both parts by $r!$, we get

$$ \frac{r^n}{r!} = \sum\limits_{k=1}^n \left\{\begin{matrix} n \\ k\end{matrix}\right\} \frac{1}{(r-k)!}. $$ Right-hand side can be perceived as a convolution of the sequences $a_k = \left\{\begin{matrix} n \\ k\end{matrix}\right\} $ and $b_k = \frac{1}{k!}$, thus

$$ \sum\limits_{r=0}^\infty \frac{r^n}{r!} x^r = \sum\limits_{k=0}^\infty \frac{x^k}{k!} \sum\limits_{k=0}^n \left\{\begin{matrix} n \\ k\end{matrix}\right\} x^k = e^x \sum\limits_{k=0}^n \left\{\begin{matrix} n \\ k\end{matrix}\right\} x^k. $$ Multiplying both sides with $e^{-x}$ yields the required identity. I wrote a more detailed explanations for generating functions of Stirling numbers of the first and of the second kind with fixed here.