2
$\begingroup$

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

$\endgroup$
2
  • $\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.defaoite
    Commented Jun 24, 2023 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$ Commented Jul 2, 2023 at 8:35

2 Answers 2

1
+100
$\begingroup$

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

$\endgroup$
2
  • $\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$ Commented Jul 6, 2023 at 19:36
  • $\begingroup$ @MatteoAldovardi You are welcome ! $\endgroup$ Commented Jul 6, 2023 at 19:37
0
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .