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}. $$
-
$\begingroup$ 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. $\endgroup$– K.defaoiteJun 24 at 16:16
-
$\begingroup$ @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$$ $\endgroup$– Matteo AldovardiJul 2 at 8:35
2 Answers
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 }$$
-
$\begingroup$ 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! $\endgroup$ Jul 6 at 19:36
-
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.
