# Proof strategy - exponential generating functions

Can anyone suggest how to touch this?

Prove that if sequences $a, b$ satisfy: $$b_{n} = \sum_{k}^{}\left[n\atop k\right]a_{k}$$ then this equation is correct for their exponential generating functions $A, B$: $$B(x) = A\left(\log\frac{1}{1-x}\right)$$

Where $\left[n\atop k\right]$ are Stirling numbers of the first kind.

I would be grateful for any help.

-
What result do you know about Stirling numbers of the first kind and generating functions? –  Did Mar 15 '12 at 17:50
Do you know the exponential generating function $$\left(\ln\frac1{1-x}\right)^m=m!\sum_{n\ge 0}\left[n\atop m\right]\frac{x^n}{n!}\;?$$ –  Brian M. Scott Mar 15 '12 at 18:06
Re proof strategy, the result is a consequence of an interversion of the order of summations in a double summation--as I am ready to explain if you answer my first comment. –  Did Mar 15 '12 at 20:26
Here's what I've got so far: $$B(n) = \sum_{n}^{}b_{n} \frac{x^{n}}{n!} = \sum_{n}^{}\sum_{k}^{}\left[n\atop k\right]a_{k} \frac{x^{n}}{n!} = \sum_{n}^{}\sum_{k}^{}a_{k}\left[n\atop k\right]\frac{x^{k}}{k!} =\ ?$$ I understand that I need to change the order of summation, and therefore I'll be able to use a formula mentioned by Brian, and finally get $$\sum_{n}^{}a_{n}\frac{(\log\frac{1}{1-x})^{n}}{n!} = A(\log\frac{1}{1-x})$$ But how do I do that? I don't understand how to change summation from the lower argument of a Stirling number to the upper one, so it will fit the formula.. –  Maria McKee Mar 15 '12 at 21:07
And answering the first question, I'm familiar with several formulas regarding Stirling numbers and generating functions. My source - Concrete Mathematics - is actually full of them:) –  Maria McKee Mar 15 '12 at 21:14

Let $A(x)$ be the exponential generating function for $a_n$, i.e. $\frac{d^n}{dx^n}A(0)=a_n$, and let $B(x)=A(\log(\frac{1}{1-x}))$.

We need to show that $\frac{d^n}{dx^n}B(0)=b_n$.

Let us find an expression for $\frac{d^n}{dx^n}B(x)$ using Stirling coefficients: $$\frac{d^n}{dx^n}B(x)=\sum_{k=1}^n\left[\matrix{n\\k}\right]a_k^n(x)A^{(k)}(-\log(1-x)).$$

We have $$\frac{d^{n+1}}{dx^{n+1}}B(x)=\sum_{k=1}^n\left[\matrix{n \\ k}\right]\left(a_k^{n'}(x)A^{(k)}(-\log(1-x))+\frac{a_k^n(x)}{1-x}A^{(k+1)}(-\log(1-x))\right)=a_1^{n'}(x)A^{(1)}(-\log(1-x))+\frac{a_n^n(x)}{1-x}A^{(n+1)}(-\log(1-x))+\sum_{k=2}^n\left(\left[\matrix{n \\ k}\right]a_k^{n'}(x)+\left[\matrix{n \\ k-1}\right]\frac{a_{k-1}^n(x)}{1-x}\right)A^{(k)}(-\log(1-x))=\sum_{k=1}^{n+1}\left(\left[\matrix{n \\ k}\right]a_k^{n'}(x)+\left[\matrix{n \\ k-1}\right]\frac{a_{k-1}^n(x)}{1-x}\right)A^{(k)}(-\log(1-x))$$

So we need $a_k^n(x)$ to be such that $\left[\matrix{n \\ k}\right]a_k^{n'}(x)+\left[\matrix{n \\ k-1}\right]\frac{a_{k-1}^n(x)}{1-x}=\left[\matrix{n+1 \\ k}\right]a_k^{n+1}(x)$. Also, we need $a_1^1(x)=\frac{1}{1-x}$.

Note that $n\left[\matrix{n \\ k}\right]+\left[\matrix{n \\ k-1}\right]=\left[\matrix{n+1 \\ k}\right]$. Therefore, we obtain the following expressions: $$a_k^n(x)=(1-x)^{-n}$$ and $$\frac{d^n}{dx^n}B(x)=\frac{1}{(1-x)^n}\sum_{k=1}^n\left[\matrix{n\\k}\right]A^{(k)}(-\log(1-x)).$$

Now just plug in $x=0$ into the final expression.

-

The generating function of Stirling numbers of the first kind is $$\sum_{k=0}^{+\infty} u^k \sum_{n=k}^{+\infty} \frac {x^n}{n!} \left[{n\atop k}\right] = \mathrm e^{ut},\qquad\text{with}\ t=\log(1/(1-x)).$$ Expanding the exponential along the powers of $u$, this yields, for every $k\geqslant0$, $$\sum_{n=k}^{+\infty} \frac {x^n}{n!} \left[{n\atop k}\right] = \frac{t^k}{k!}.$$ Hence, $B(x)=\sum\limits_{n=0}^{+\infty} b_n\frac {x^n}{n!}$ is $$B(x)=\sum_{n=0}^{+\infty}\sum_{k=0}^n\left[{n\atop k}\right]a_k\frac {x^n}{n!}=\sum_{k=0}^{+\infty}a_k\sum_{n=k}^{+\infty}\left[{n\atop k}\right]\frac {x^n}{n!}=\sum_{k=0}^{+\infty}a_k\frac{t^k}{k!}=A(t).$$

-