Exponential Generating Functions

To form a generating function, we multiplied by $z^{N}$ and summed. This is not the only way to form a generating function. Another way is to multiply by $z^{N}/N!$ and then sum.

Then:

$\begin{equation*} \{1\}=e^{z} \end{equation*}$

$\begin{equation*} \left\{2^{N}\right\}=e^{2z} \end{equation*}$

$\begin{equation*} \{N!\}=\frac{1}{1-z} \end{equation*}$

Convolution:

$\begin{equation*} \left\{\sum_{k=0}^{n}\dbinom{n}{k}a_{k}b_{n-k}\right\}=A(z)B(z) \end{equation*}$

The proof is instructive:

$\begin{equation*} A(z)B(z)=\sum_{k\ge0}a_{k}\frac{z^{k}}{k!}\sum_{n\ge0}b_{n}\frac{z^{n}}{n!} \end{equation*}$

Reindex $n$ to $n-k$

$\begin{equation*} A(z)B(z)=\sum_{k\ge0}\sum_{n\ge k}\frac{a_{k}}{k!}\frac{b_{n-k}}{(n-k)!}z^{n} \end{equation*}$

Multiply and divide by $N!$ :

$\begin{equation*} A(z)B(z)=\sum_{k\ge0}\sum_{n\ge k}\dbinom{n}{k}a_{k}b_{n-k}\frac{z^{n}}{n!} \end{equation*}$

Change the order of summation and you get the result.

Solving a recurrence relation:

$\begin{equation*} f_{n}=\sum_{k}\dbinom{n}{k}\frac{f_{k}}{2^{k}} \end{equation*}$

This is convolution using $a_{k}=f_{k}$ and $b_{n}=2^{n}$ . To solve it, just follow the binomial convolution steps backwards:

Switch order of summation from the get-go.
Change $n$ to $n+k$ .

The solution is:

$\begin{equation*} f(z)=e^{z}f(z/2) \end{equation*}$

You can now telescope to get

$\begin{equation*} f(z)=e^{2z} \end{equation*}$

This gives:

$\begin{equation*} f_{n}=2^{n} \end{equation*}$