Confused on Exponential Generating function

Oct 2009
255
20
St. Louis Area
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.
 
Sep 2009
38
22
Rio de janeiro
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
Mar 2008
934
409
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}\)
 
  • Like
Reactions: oldguynewstudent
Oct 2009
255
20
St. Louis Area
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!