Definition
An ordinary generating function of a sequence \(\left\{a_{k}\right\}\) is:
\begin{equation*}
A(z) = \sum_{k\ge 0}a_{k}z^{k}
\end{equation*}
We use the notation \([z^{N}]A(z)\) to get the coefficient of
\(z^{N}\) in \(A(z)\).
This is a tool that converts from sequences to functions.
Examples
\begin{equation*}
\left\{1,1,\dots\right\}=\frac{1}{1-z}
\end{equation*}
\begin{equation*}
\left\{1/N!\right\}=e^{z}
\end{equation*}
Tricks To Get The Generating Function of a Sequence
Scaling
\begin{equation*}
A(cz) = \sum_{k\ge 0}c^{k}a_{k}z^{k}
\end{equation*}
Addition of Two Functions
\begin{equation*}
A(z)+B(z)=\sum_{k\ge 0}\left(a_{k}+b_{k}\right)z^{k}
\end{equation*}
If you can’t figure out the function, could it be a difference of two functions?
Differentiation
\begin{equation*}
zA'(z) = \sum_{k\ge 1}ka_{k}z^{k}
\end{equation*}
Could it have been the derivative of a known function?
Examples:
\begin{equation*}
\left\{0,1,2,3,\dots\right\}=\frac{z}{\left(1-z\right)^{2}}=z\frac{d}{dz}\frac{1}{1-z}
\end{equation*}
\begin{equation*}
\left\{\dbinom{N}{2}\right\}=\frac{z^{2}}{\left(1-z\right)^{3}}=\frac{1}{2}z^{2}\frac{d^{2}}{dz^{2}}\frac{1}{1-z}
\end{equation*}
\begin{equation*}
\left\{\dbinom{N}{M}\right\}=\frac{z^{M}}{\left(1-z\right)^{M+1}}=\frac{z^{M}}{M!}\frac{d^{M}}{dz^{M}}\frac{1}{1-z}
\end{equation*}
\begin{equation*}
\left\{\dbinom{N+M}{M}\right\}=\frac{1}{\left(1-z\right)^{M+1}}=\frac{1}{M!}\frac{d^{M}}{dz^{M}}\frac{1}{1-z}
\end{equation*}
Integration
\begin{equation*}
\int_{0}{z}A(t)dt = \sum_{k\ge 1}\frac{a_{k-1}}{k}z^{k}
\end{equation*}
Examples:
\begin{equation*}
\left\{\frac{1}{N}\right\}=\ln\frac{1}{1-z}
\end{equation*}
Partial Sums
\begin{equation*}
\left\{\sum_{k=0}^{k=n}a_{k}\right\}=\frac{1}{1-z}A(z)
\end{equation*}
To prove this, write the RHS as a product of two sums, combine, and
change the order of summation (also may need to reindex to finally get
\(z^{n}\)).
\begin{equation*}
\left\{H_{N}\right\}=\frac{1}{1-z}\ln\frac{1}{1-z}
\end{equation*}
where \(H_{N}\) is the sum of the harmonic sequence.
Convolution
\begin{equation*}
\left\{\sum_{k=0}^{k=n}a_{k}b_{n-k}\right\}=A(z)B(z)
\end{equation*}
Expansion
Do a Taylor/Mclaurin expansion.
Notes
The techniques on this page allow you to derive some identities. A
technique will give you one result for the coefficient of \(z^{N}\),
and simply doing a Mclaurin expansion on the generating function may
yield a different expression. Setting the two together gives you an identity.
An example is:
\begin{equation*}
\sum_{k=1}^{N}H_{k}=\left(N+1\right)\left(H_{N+1}-1\right)
\end{equation*}
It’s not hard to show that the LHS is:
\begin{equation*}
\frac{1}{\left(1-z\right)^{2}}\ln\frac{1}{1-z}
\end{equation*}
Do a Mclaurin expansion to get the RHS.