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*}