# Confused on Exponential Generating function

#### oldguynewstudent

Given the following notation: $$\displaystyle \left[\left[f(x)\right]\right]_{x^{k}}$$ = the coefficient of $$\displaystyle x^{k}$$ in f(x).

Also for an exponential generating function $$\displaystyle \left[\left[e^{x}\right]\right]_{\frac{x^{k}}{k!}}$$=$$\displaystyle \left[\left[\sum_{k\geq0}\frac{x^{k}}{k!}\right]\right]_{\frac{x^{k}}{k!}}=1$$.

We have an example in Combinatorics A Guided Tour by David R. Mazur p. 129-130 as follows:

Find a formula for the n-th term of the sequence $$\displaystyle \{d_{n}\}_{n\geq0}$$ defined by $$\displaystyle d_{0}=1\,\, d_{n}=nd_{n-1}+1\,\,\, n\geq1$$.

After a short derivation we have $$\displaystyle d_{n}=\left[\left[e^{x}*\frac{1}{1-x}\right]\right]_{\frac{x^{n}}{n!}}$$=$$\displaystyle \sum_{j=0}^{n}\left({n\atop j}\right)1*(n-j)!$$=$$\displaystyle \sum_{j=0}^{n}\left({n\atop j}\right)(n-j)!$$

I am familiar with $$\displaystyle (1+x)^{n}=\sum_{k\geq0}\left({n\atop k}\right)x^{k}$$. Also I know $$\displaystyle \frac{1}{1-x}=\sum_{k\geq0}k!\frac{x^{k}}{k!}$$. But I just do not see how the binomial fits into the above summation.

I have been working almost nonstop on this course and applied statistics this summer. Any help with how the binomial gets into the above summation would be greatly appreciated. By the way, this is the most fascinating course I have ever taken even though I seem to be struggling just a little.

#### Renji Rodrigo

In this case you can use the cauchy product of the series

Given two series $$\displaystyle \sum\limits^{\infty}_{k=0}a_{k}$$

and $$\displaystyle \sum\limits^{\infty}_{k=0}b_{k}$$ , the Cauchy product is

$$\displaystyle \sum\limits^{\infty}_{k=0}c_{k}$$

where

$$\displaystyle c_{n}= \sum\limits^{n}_{k=0}a_{k}b_{n-k}\;\;n \in N.$$

#### awkward

MHF Hall of Honor
Hi oldguynewstudent,

I think the theorem you need is that if
$$\displaystyle f(x) = \sum_{n=0}^{\infty} \frac{a_n}{n!} x^n$$
and
$$\displaystyle g(x) = \sum_{n=0}^{\infty} \frac{b_n}{n!} x^n$$
then the coefficient of $$\displaystyle \frac{x^n}{n!}$$ in $$\displaystyle f(x) \cdot g(x)$$
is
$$\displaystyle \sum_r \binom{n}{r} a_r b_{n-r}$$

• oldguynewstudent

#### oldguynewstudent

Hi oldguynewstudent,

I think the theorem you need is that if
$$\displaystyle f(x) = \sum_{n=0}^{\infty} \frac{a_n}{n!} x^n$$
and
$$\displaystyle g(x) = \sum_{n=0}^{\infty} \frac{b_n}{n!} x^n$$
then the coefficient of $$\displaystyle \frac{x^n}{n!}$$ in $$\displaystyle f(x) \cdot g(x)$$
is
$$\displaystyle \sum_r \binom{n}{r} a_r b_{n-r}$$
Yes, that is what I was looking for!