The most basic tool used to express generating functions in closed form is the closed form expression for the geometric series, which is an expression of the form \(a + a r + a r^2+ \cdots\text{.}\) It can either be terminated or extended infinitely.
Infinite Geometric Series:
\begin{gather}
a + a r + a r^2+ \cdots = \frac{a}{1r}\tag{8.5.19}
\end{gather}
These restrictions don’t come into play with generating functions. We could derive
(8.5.18) by noting that if
\(S(n) = a + a r +\cdots + a r^n\text{,}\) \(n
> 0\text{,}\) then
\(S(n) = r S(n  1) + a\) (See Exercise 10 of Section 8.3). An alternative derivation was used in Section 8.4. We will take the same steps to derive
(8.5.19). Let
\(x = a + a r + a r^2 + \cdots \text{.}\) Then
\begin{equation*}
r x =a r+ ar^2 +\cdots = x a \Rightarrow xrx=a \Rightarrow x= \frac{a}{1r}
\end{equation*}
Solve \(S(k) + 3S(k  1)  4S(k 2) = 0\text{,}\) \(k\geq 2\text{,}\) with \(S(0) = 3\) and \(S(1) = 2\text{.}\) The solution will be derived using the same steps that were used earlier in this section, with one variation.
Translate to an equation about generating functions. First, we change the index of the recurrence relation by substituting \(n + 2\) for \(k\text{.}\) The result is \(S(n + 2) + 3S(n + 1)  4S(n) = 0\text{,}\) \(n \geq 0\text{.}\) Now, if \(V(n) = S(n + 2) + 3 S(n + 1)  4S(n)\text{,}\) then \(V\) is the zero sequence, which has a zero generating function. Furthermore, \(V = S\uparrow 2+3(S\uparrow )4 S\text{.}\) Therefore,
\begin{equation*}
\begin{split}
0 &= G(V;z) \\
& = G(S\uparrow 2; z) + 3 G(S\uparrow ;z)  4G(S;z) \\
& = \frac{G(S;z)  S(0)  S(1)z }{z^2}+4 \frac{(G(S;z)  S(0))}{z}  4G(S;z)\\
\end{split}
\end{equation*}
We want to now solve the following equation for \(G(S;z)\text{:}\)
\begin{equation*}
\frac{G(S;z)  S(0)  S(1)z }{z^2}+4 \frac{(G(S;z)  S(0))}{z}  4G(S;z) = 0
\end{equation*}
Multiply by \(z^2\) :
\begin{equation*}
G(S;z)  3 + 2z + 3z(G(S;z)  3)  4z^2 G(S;z) = 0
\end{equation*}
Expand and collect all terms involving \(G(S;z)\) on one side of the equation:
\begin{equation*}
\begin{array}{c}
G(S;z) + 3z G(S;z)  4z^2 G(S;z) = 3 + 7z\\
\left(1 + 3z  4z^2 \right)G(S;z)= 3 + 7z\\
\end{array}
\end{equation*}
Therefore,
\begin{equation*}
G(S;z)= \frac{3+7z}{1 + 3z  4z^2}
\end{equation*}
Determine S from its generating function. \(1 + 3z  4z^2 = (1 + 4z) (1  z)\) thus a partial fraction decomposition of \(G(S;z)\) would be:
\begin{equation*}
\frac{A}{1+4z}+ \frac{B}{1z}=\frac{A zA4 B zB}{(z1) (4 z+1)} =\frac{(A+B)+(4BA)z}{(z1) (4 z+1)}
\end{equation*}
Therefore, \(A + B = 3\) and \(4B  A = 7\text{.}\) The solution of this set of equations is \(A = 1\) and \(B = 2\text{.}\) \(G(S;z)= \frac{1}{1+4z}+ \frac{2}{1z}\text{.}\)
\begin{equation*}
\begin{array}{c}
\frac{1}{1+4z} \textrm{ is the generating function of }S_1(n)=(4)^n\textrm{, and}\\
\frac{2}{1z} \textrm{ is the generating function of }S_2(n) = 2(1)^n = 2\\
\end{array}
\end{equation*}
In conclusion, since \(G(S;z) = G\left(S_1;z\right) + G\left(S _2;z\right)\text{,}\) \(S(n) = 2 + (4)^n\text{.}\)
Let \(A = \{a, b, c, d, e\}\) and let \(A^*\) be the set of all strings of length zero or more that can be made using each of the elements of \(A\) zero or more times. By the generalized rule of products, there are \(5^n\) such strings that have length \(n\text{,}\) \(n\geq 0\text{,}\) Suppose that \(X_n\) is the set of strings of length \(n\) with the property that all of the \(a\)’s and \(b\)’s precede all of the \(c\)’s, \(d\)’s, and \(e\)’s. Thus \(aaabde \in X_6\text{,}\) but \(abcabc \notin X_6\text{.}\) Let \(R(n) =\lvert X_n \rvert\text{.}\) A closed form expression for \(R\) can be obtained by recognizing \(R\) as the convolution of two sequences. To illustrate our point, we will consider the calculation of \(R(6)\text{.}\)
Note that if a string belongs to \(X_6\text{,}\) it starts with \(k\) characters from \(\{a, b\}\) and is followed by \(6  k\) characters from \(\{c,
d, e\}\text{.}\) Let \(S(k)\) be the number of strings of \(a\)’s and \(b\)’s with length \(k\) and let \(T(k)\) be the number of strings of \(c\)’s, \(d\)’s, and \(e\)’s with length \(k\text{.}\) By the generalized rule of products, \(S(k) = 2^k\) and \(T(k) = 3^k\text{.}\) Among the strings in \(X_6\) are the ones that start with two \(a\)’s and \(b\)’s and end with \(c\)’s, \(d\)’s, and \(e\)’s. There are \(S(2)T(4)\) such strings. By the law of addition,
\begin{equation*}
\lvert X_6 \rvert =R(6)=S(0)T(6)+S(1)T(5)+\cdots +S(5)T(1)+S(6)T(0)
\end{equation*}
Note that the sixth term of R is the sixth term of the convolution of \(S\) with \(T\text{,}\) \(S*T\text{.}\) Think about the general situation for a while and it should be clear that \(R =S*T\text{.}\) Now, our course of action will be to:
Determine the generating functions of \(S\) and \(T\text{,}\)
Multiply \(G(S;z)\) and \(G(T;z)\) to obtain \(G(S*T;z) = G(R;z)\text{,}\) and
Determine \(R\) on the basis of \(G(R;z)\text{.}\)
\(G(S;z) =\sum_{k=0}^{\infty} 2^k z^k=\frac{1}{12z}\) , and \(G(T;z) =\sum_{k=0}^{\infty} 3^k z^k=\frac{1}{13z}\)
\(\displaystyle G(R;z) = G(S;z)G(T;z) = \frac{1}{(12z)(13z)}\)

To recognize \(R\) from \(G(R;z)\text{,}\) we must do a partial fractions decomposition:
\begin{equation*}
\frac{1}{(12z)(13z)}=\frac{A}{12z}+\frac{B}{13z}=\frac{3 A z+A2 B z+B}{(2 z1) (3 z1)}=\frac{(A+B)+(3 A 2 B )z}{(2 z1) (3 z1)}
\end{equation*}
Therefore, \(A + B = 1\) and \(3A  2B = 0\text{.}\) The solution of this pair of equations is \(A =  2\) and \(B = 3\text{.}\) Since \(G(R;z) =\frac{2}{12z}+\frac{3}{13z}\text{,}\) which is the sum of the generating functions of \(2(2)^k\) and \(3 (3)^k\text{,}\) \(R(k) =2(2)^k+3 (3)^k = 3^{k+1}2^{k+1}\)
For example, \(R(6) = 3^7  2^7= 2187  128 = 2059\text{.}\) Naturally, this equals the sum that we get from \((S*T)(6)\text{.}\) To put this number in perspective, the total number of strings of length 6 with no restrictions is \(5^6=15625\text{,}\) and \(\frac{2059}{15625}\approx 0.131776\text{.}\) Therefore approximately 13 percent of the strings of length 6 satisfy the conditions of the problem.