# Formula involving the Stirling numbers of the second kind

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}.$$

• HINT: Let $$a_n(x)=\sum_{k=1}^n S(n,k)x^k \\ b_n(x)=\mathrm e^{-x}\sum_{k=1}^\infty \frac{k^n}{k!}x^k$$ Show first that $a_1(x)=b_1(x)$ (easy) then show that $a$ and $b$ follow the same recursion. Jun 24 at 16:16
• @K.defaoite all I get is $$\Big\{ \begin{matrix} n \\ k \end{matrix} \Big\} = \sum_{s=0}^{k} \dfrac{(-1)^{k-s}}{s!} \cdot \dfrac{(k-s)^{n}}{(k-s)!} = \frac{1}{k!} \cdot \sum_{s=0}^{k} (-1)^{k-s}\cdot \binom{k}{s}\cdot (k-s)^{n},$$ and $$\Big\{ \begin{matrix} n \\ 1 \end{matrix} \Big\}=1$$ Jul 2 at 8:35

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 }$$

• Ironically, I was in the process of deriving the explicit formula from the generating function of the Stirling numbers just before I read your answer. Thanks for the help! Jul 6 at 19:36
• @MatteoAldovardi You are welcome ! Jul 6 at 19:37

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.