Skip to main content
\(\newcommand{\set}[1]{\{1,2,\dotsc,#1\,\}} \newcommand{\ints}{\mathbb{Z}} \newcommand{\posints}{\mathbb{N}} \newcommand{\rats}{\mathbb{Q}} \newcommand{\reals}{\mathbb{R}} \newcommand{\complexes}{\mathbb{C}} \newcommand{\twospace}{\mathbb{R}^2} \newcommand{\threepace}{\mathbb{R}^3} \newcommand{\dspace}{\mathbb{R}^d} \newcommand{\nni}{\mathbb{N}_0} \newcommand{\nonnegints}{\mathbb{N}_0} \newcommand{\dom}{\operatorname{dom}} \newcommand{\ran}{\operatorname{ran}} \newcommand{\prob}{\operatorname{prob}} \newcommand{\Prob}{\operatorname{Prob}} \newcommand{\height}{\operatorname{height}} \newcommand{\width}{\operatorname{width}} \newcommand{\length}{\operatorname{length}} \newcommand{\crit}{\operatorname{crit}} \newcommand{\inc}{\operatorname{inc}} \newcommand{\HP}{\mathbf{H_P}} \newcommand{\HCP}{\mathbf{H^c_P}} \newcommand{\GP}{\mathbf{G_P}} \newcommand{\GQ}{\mathbf{G_Q}} \newcommand{\AG}{\mathbf{A_G}} \newcommand{\GCP}{\mathbf{G^c_P}} \newcommand{\PXP}{\mathbf{P}=(X,P)} \newcommand{\QYQ}{\mathbf{Q}=(Y,Q)} \newcommand{\GVE}{\mathbf{G}=(V,E)} \newcommand{\HWF}{\mathbf{H}=(W,F)} \newcommand{\bfC}{\mathbf{C}} \newcommand{\bfG}{\mathbf{G}} \newcommand{\bfH}{\mathbf{H}} \newcommand{\bfF}{\mathbf{F}} \newcommand{\bfI}{\mathbf{I}} \newcommand{\bfK}{\mathbf{K}} \newcommand{\bfP}{\mathbf{P}} \newcommand{\bfQ}{\mathbf{Q}} \newcommand{\bfR}{\mathbf{R}} \newcommand{\bfS}{\mathbf{S}} \newcommand{\bfT}{\mathbf{T}} \newcommand{\bfNP}{\mathbf{NP}} \newcommand{\bftwo}{\mathbf{2}} \newcommand{\cgA}{\mathcal{A}} \newcommand{\cgB}{\mathcal{B}} \newcommand{\cgC}{\mathcal{C}} \newcommand{\cgD}{\mathcal{D}} \newcommand{\cgE}{\mathcal{E}} \newcommand{\cgF}{\mathcal{F}} \newcommand{\cgG}{\mathcal{G}} \newcommand{\cgM}{\mathcal{M}} \newcommand{\cgN}{\mathcal{N}} \newcommand{\cgP}{\mathcal{P}} \newcommand{\cgR}{\mathcal{R}} \newcommand{\cgS}{\mathcal{S}} \newcommand{\bfn}{\mathbf{n}} \newcommand{\bfm}{\mathbf{m}} \newcommand{\bfk}{\mathbf{k}} \newcommand{\bfs}{\mathbf{s}} \newcommand{\bijection}{\xrightarrow[\text{onto}]{\text{$1$--$1$}}} \newcommand{\injection}{\xrightarrow[]{\text{$1$--$1$}}} \newcommand{\surjection}{\xrightarrow[\text{onto}]{}} \newcommand{\nin}{\not\in} \newcommand{\prufer}{\mbox{prüfer}} \DeclareMathOperator{\fix}{fix} \DeclareMathOperator{\stab}{stab} \DeclareMathOperator{\var}{var} \newcommand{\inv}{^{-1}} \newcommand{\lt}{<} \newcommand{\gt}{>} \newcommand{\amp}{&} \)

Section9.6Using generating functions to solve recurrences

The approach we have seen thus far in this chapter is not the only way to solve recurrence equations. Additionally, it really only applies to linear recurrence equations with constant coefficients. In the remainder of the chapter, we will look at some examples of how generating functions can be used as another tool for solving recurrence equations. In this section, our focus will be on linear recurrence equations. In Section 9.7, we will see how generating functions can solve a nonlinear recurrence.

Our first example is the homogeneous recurrence that corresponds to the advancement operator equation in Example 9.9.

Example9.24

Consider the recurrence equation \(r_{n}+r_{n-1}-6r_{n-2} = 0\) for the sequence \(\{r_n\colon n\geq 0\}\) with \(r_0=1\) and \(r_1=3\text{.}\) This sequence has generating function \begin{equation*} f(x) = \sum_{n=0}^\infty r_n x^n = r_0+r_1 x+r_2x^2+r_3x^3+\cdots. \end{equation*} Now consider for a moment what the function \(xf(x)\) looks like. It has \(r_{n-1}\) as the coefficient on \(x_n\text{.}\) Similarly, in the function \(-6x^2 f(x)\text{,}\) the coefficient on \(x^n\) is \(-6r_{n-2}\text{.}\)

What is our point in all of this? Well, if we add them all up, notice what happens. The coefficient on \(x_n\) becomes \(r_n+r_{n-1}-6r_{n-2}\text{,}\) which is \(0\) because of the recurrence equation! Now let's see how this all lines up: \begin{align*} f(x) \amp = r_0 + r_1 x + r_2x^2 + r_3 x^3 + \cdots + r_nx^n + \cdots\\ xf(x) \amp = 0 + r_0 x + r_1x^2 + r_2 x^3 + \cdots r_{n-1}x^n + \cdots\\ -6x^2f(x) \amp = 0 + 0 -6r_0x^2 - 6r_1 x^3 + \cdots - 6r_{n-2}x^n + \cdots \end{align*} When we add the left-hand side, we get \(f(x)(1+x-6x^2)\text{.}\) On the right-hand side, the coefficient on \(x^n\) for \(n\geq 2\) is \(0\) because of the recurrence equation. However, we are left with \(r_0 + (r_0+r_1)x = 1 + 4x\text{,}\) using the initial conditions. Thus, we have the equation \begin{equation*} f(x)(1+x-6x^2)= 1+4x, \end{equation*} or \(f(x) = (1+4x)/(1+x-6x^2)\text{.}\) This is a generating function that we can attack using partial fractions, and we find that \begin{equation*} f(x) = \frac{6}{5}\frac{1}{1-2x}-\frac{1}{5}\frac{1}{1+3 x} = \frac{6}{5}\sum_{n=0}^\infty 2^n x^n -\frac{1}{5} \sum_{n=0}^\infty (-3)^n x^n. \end{equation*} From here, we read off \(r_n\) as the coefficient on \(x^n\) and have \(r_n = (6/5) 2^n -(1/5)(-3)^n\text{.}\)

Although there's a bit more work involved, this method can be used to solve nonhomogeneous recurrence equations as well, as the next example illustrates.

Example9.25

The recurrence equation \(r_n - r_{n-1}-2r_{n-2} = 2^n\) is nonhomogeneous. Let \(r_0=2\) and \(r_1=1\text{.}\) This time, to solve the recurrence, we start by multiplying both sides by \(x^n\text{.}\) This gives the equation \begin{equation*} r_nx^n - r_{n-1}x^n-2r_{n-2}x^n = 2^nx^n. \end{equation*} If we sum this over all values of \(n\geq 2\text{,}\) we have \begin{equation*} \sum_{n=2}^\infty r_nx^n - \sum_{n=2}^\infty r_{n-1}x^n-2 \sum_{n=2}^\infty r_{n-2}x^n = \sum_{n=2}^\infty 2^nx^n. \end{equation*} The right-hand side you should readily recognize as being almost equal to \(1/(1-2x)\text{.}\) We are missing the \(1\) and \(2x\) terms, however, so must subtract them from the rational function form of the series. On the left-hand side, however, we need to do a bit more work.

The first sum is just missing the first two terms of the series, so we can replace it by \(R(x) - (2+x)\text{,}\) where \(R(x)=\sum_{n=0}^\infty r_n x^n\text{.}\) The second sum is almost \(xR(x)\text{,}\) except it's missing the first term. Thus, it's equal to \(xR(x) - 2x\text{.}\) The sum in the final term is simply \(x^2 R(x)\text{.}\) Thus, the equation can be rewritten as \begin{equation*} R(x) - (2+x) -(xR(x)-2x)-2x^2R(x) = \frac{1}{1-2x} - 1- 2x. \end{equation*} A little bit of algebra then gets us to the generating function \begin{equation*} R(x) = \frac{6x^2-5x+2}{2(1-2x)(1-x-2x^2)}. \end{equation*} This generating function can be expanded using partial fractions, so we have \begin{align*} R(x) \amp = -\frac{1}{9(1-2x)} + \frac{2}{3(1-2x)^2} + \frac{13}{9(1+x)}\\ \amp = -\frac{1}{9} \sum_{n=0}^\infty 2^nx^n + \frac{2}{3}\sum_{n=0}^\infty n2^{n-1} x^{n-1} + \frac{13}{9}\sum_{n=0}^\infty (-1)^n. \end{align*} From this generating function, we can now read off that \begin{equation*} r_n = -\frac{1}{9}2^n + \frac{2(n+1)}{3}2^{n} + \frac{13}{9}(-1)^n = \frac{5}{9} 2^n + \frac{2}{3}n2^n + \frac{13}{9}(-1)^n. \end{equation*}

The recurrence equations of the two examples in this section can both be solved using the techniques we studied earlier in the chapter. One potential benefit to the generating function approach for nonhomogeneous equations is that it does not require determining an appropriate form for the particular solution. However, the method of generating functions often requires that the resulting generating function be expanded using partial fractions. Both approaches have positives and negatives, so unless instructed to use a specific method, you should choose whichever seems most appropriate for a given situation. In the next section, we will see a recurrence equation that is most easily solved using generating functions because it is nonlinear.