How to find an exponential generating function if we know a usual generating function?

245 Views Asked by At

Suppose we know a usual generating function of a sequence $a_0,a_1, a_2 \ldots :$ $$ f(x)=a_0+a_1 x+a_2 x^2+\cdots, $$

Question. It is possible to find an exponential generating function for the sequence $a_0,a_1,a_2 \ldots $ if we know its usual generating function?

2

There are 2 best solutions below

2
On BEST ANSWER

Let $C$ be any contour in the complex plane surrounding the origin counter-clockwisely once.
We have this little identity $$\frac{x^k}{k!} = \frac{1}{2\pi i}\int_C \frac{e^{xt}}{t^{k+1}} dt$$

Given an OGF $f(x) = \sum_{k=0}^\infty a_k x^k$, we can "formally" construct the corresponding EGF as

$$\begin{align} f_{\rm EGF}(x) \stackrel{def}{=} \sum_{k=0}^\infty a_k \frac{x^k}{k!} & = \sum_{k=0}^\infty a_k \left(\frac{1}{2\pi i}\int_C \frac{e^{xt}}{t^{k+1}} dt\right) = \frac{1}{2\pi i}\int_{C} \sum_{k=0}^\infty \frac{a_k e^{xt}}{t^{k+1}} dt\\ &= \frac{1}{2\pi i}\int_{C} f\left(\frac{1}{t}\right)\frac{e^{xt}}{t} dt \end{align} $$ The integral on RHS depends on $C$. To find the correct EGF, we need to use the right contour.

Let us use the case $a_k = 1$ for all $k$ as an example. We know the corresponding OGF $g(x)$ is $\frac{1}{1-x}$. Substitute this in above formula, the corresponding EGF becomes

$$g_{\rm EGF}(x) = \frac{1}{2\pi i}\int_C \frac{1}{1 - 1/t} \frac{e^{xt}}{t} dt = \frac{1}{2\pi i}\int_C \frac{e^{xt}}{t - 1} dt $$ In order for the sequence $\sum_{k=0}^\infty x^k$ converges to $g(x)$,we need $|x| < 1$. This means $$|1/t| < 1 \quad\iff\quad |t| > 1\quad\text{ on }C.$$ As a result, the contour $C$ we need is the one which include $t = 1$ in its interior. Using such a contour, we find the correct EGF for this example: $$g_{\rm EGF}(x) = {\rm Res}( e^{xt} ; t = 1 ) = e^{x}.$$

0
On

Let $f(z)$ be the ordinary generating function and $\mathcal{L}$ be the Laplace transform. Then the EGF $g(z)$ has the form $$ g(z)=\mathcal{L}^{-1}\left(\frac{1}{z} f(z)\Big |_{z=\frac{1}{z}}\right) $$