Product of Exponential Generating Functions

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $G \left({z}\right)$ be the exponential generating function for the sequence $\left\langle{\dfrac {a_n} {n!} }\right\rangle$.

Let $H \left({z}\right)$ be the exponential generating function for the sequence $\left\langle{\dfrac {b_n} {n!} }\right\rangle$.


Then $G \left({z}\right) H \left({z}\right)$ is the generating function for the sequence $\left\langle{\dfrac {c_n} {n!} }\right\rangle$, where:

$\forall n \in \Z_{\ge 0}: c_n = \displaystyle \sum_{k \mathop \in \Z} \dbinom n k a_k b_{n - k}$


Proof

Let $G \left({z}\right) H \left({z}\right)$ be the generating function for the sequence $\left\langle{c'_n}\right\rangle$.


By definition of generating function:

\(\ds G \left({z}\right) H \left({z}\right)\) \(=\) \(\ds \sum_{k \mathop \ge 0} \dfrac {a_k} {k!} z^k \sum_{k \mathop \ge 0} \dfrac {b_k} {k!} z^k\)
\(\ds \) \(=\) \(\ds \left({\dfrac {a_0} {0!} + \dfrac {a_1} {1!} z + \dfrac {a_2} {2!} z^2 + \cdots}\right) \left({\dfrac {b_0} {0!} + \dfrac {b_1} {1!} z + \dfrac {b_2} {2!} z^2 + \cdots}\right)\)


Then:

\(\ds c'_n\) \(=\) \(\ds \sum_{k \mathop = 0}^n \dfrac {a_k} {k!} \dfrac {b_{n - k} } {\left({n - k}\right)!}\) Product of Generating Functions
\(\ds \) \(=\) \(\ds \dfrac 1 {n!} \left({\sum_{k \mathop = 0}^n \dfrac {n!} {k! \left({n - k}\right)!} a_k b_{n - k} }\right)\)
\(\ds \) \(=\) \(\ds \dfrac 1 {n!} \left({\sum_{k \mathop = 0}^n \dbinom n k a_k b_{n - k} }\right)\) Definition 1 of Binomial Coefficient/Integers
\(\ds \) \(=\) \(\ds \dfrac {c_n} {n!}\) where $c_n = \displaystyle \sum_{k \mathop = 0}^n \dbinom n k a_k b_{n - k}$

Hence the result.

$\blacksquare$


Sources