Ordinary Generating Function

216 Views Asked by At

Wondering how to tackle this problem which appears to be a sum inside of a sum for a generating function. Thank you!

Find an ordinary generating function for the sequence whose kth term is

$(a_k)$ = $\dfrac{1}{0!} + \dfrac{1}{1!} + \dfrac{1}{2!} + \ldots + \dfrac{1}{k!}$

1

There are 1 best solutions below

0
On

We know that $$ e^x = \sum\limits_{k \geq 0} \frac{x^k}{k!} $$ i.e. $e^x$ is the ordinary generating function for $\frac{1}{k!}$. If we multiply this by $\frac{1}{1 - x}$ we have \begin{align} \frac{e^x}{1 - x} &= \left(\sum\limits_{k \geq 0} \frac{1}{k!} x^k \right)\left(\sum\limits_{k \geq 0} x^k \right) \\ &= \sum\limits_{k \geq 0} \left(\sum\limits_{j = 0}^k \frac{1}{j!}\right)x^k. \end{align}

Thus, $\frac{e^x}{1 - x}$ is what we're looking for.

In general, if $F(x)$ is the ordinary generating function for $\{b_k\}$, then $\frac{F(x)}{1 - x}$ is the ordinary generating function for $\left\{\sum\limits_{j = 0}^k b_j \right\}$.