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.4Solving advancement operator equations

In this section, we will explore some ways of solving advancement operator equations. Some we will make up just for the sake of solving, while others will be drawn from the examples we developed in Section 9.1. Again, readers familiar with differential equations will notice many similarities between the techniques used here and those used to solve linear differential equations with constant coefficients, but we will not give any further examples to make those parallels explicit.

Subsection9.4.1Homogeneous equations

Homogeneous equations, it will turn out, can be solved using very explicit methodology that will work any time we can find the roots of a polynomial. Let's start with another fairly straightforward example.

Example9.9

Find all solutions to the advancement operator equation \begin{equation} (A^2+A-6)f = 0. \label{eqn_recurrence_deg2}\tag{9.4.1} \end{equation}

Solution

What happened in this example is far from a fluke. If you have an advancement operator equation of the form \(p(A)f=0\) (the constant term of \(p\) nonzero) and \(p\) has degree \(k\text{,}\) then the general solution of \(p(A)f=0\) will be a \(k\)-parameter family (in the previous example, our parameters are the constants \(c_1\) and \(c_2\)) whose terms come from solutions to simpler equations arising from the factors of \(p\text{.}\) We'll return to this thought in a little bit, but first let's look at another example.

Example9.10

Let's revisit the problem of enumerating ternary strings of length \(n\) that do have \((2,0)\) occurring as a substring in two consecutive positions that we encountered in Example 9.4. There we saw that this number satisfies the recurrence equation \begin{equation*} t_{n+2} = 3t_{n+1} - t_n,\qquad n\geq 1 \end{equation*} and \(t_1 = 3\) and \(t_2=8\text{.}\) Before endeavoring to solve this, let's rewrite our recurrence equation as an advancement operator equation. This gives us \begin{equation} p(A)t=(A^2-3A+1)t=0. \label{eqn_recurrence_ternary}\tag{9.4.2} \end{equation}

The roots of \(p(A)\) are \((3\pm\sqrt{5})/2\text{.}\) Following the approach of the previous example, our general solution is \begin{equation*} t(n) = c_1\left(\frac{3+\sqrt{5}}{2}\right)^n + c_2\left(\frac{3-\sqrt{5}}{2}\right)^n. \end{equation*} This probably looks suspicious; we're counting strings here, so \(t(n)\) needs to be a nonnegative integer, but the form we've given includes not just fractions but also square roots! However, if you look carefully, you'll see that using the binomial theorem to expand the terms in our expression for \(t(n)\) would get rid of all the square roots, so everything is good. (A faster way to convince yourself that this really satisfies Equation (9.4.2) is to mimic the verification we used in the previous example.) Because we have initial values for \(t(n)\text{,}\) we are able to solve for \(c_1\) and \(c_2\) here. Evaluating at \(n=0\) and \(n=1\) we get \begin{align*} 3 \amp = c_1 + c_2\\ 8 \amp = c_1\frac{3+\sqrt{5}}{2} + c_2 \frac{3-\sqrt{5}}{2}. \end{align*} A little bit of computation gives \begin{equation*} c_1 = \frac{7\sqrt{5}}{10} + \frac{3}{2} \quad\text{and} \quad c_2 = -\frac{7\sqrt{5}}{10} +\frac{3}{2} \end{equation*} so that \begin{equation*} t(n) = \left(\frac{7\sqrt{5}}{10} + \frac{3}{2}\right) \left(\frac{3+\sqrt{5}}{2}\right)^n+ \left(-\frac{7\sqrt{5}}{10} +\frac{3}{2}\right) \left(\frac{3-\sqrt{5}}{2}\right)^n. \end{equation*}

Example9.11

Find the general solution to the advancement operator equation \begin{equation*} (A+1)(A-6)(A+4)f = 0. \end{equation*}

Solution

By now, you should be able to see most of the pattern for solving homogeneous advancement operator equations. However, the examples we've considered thus far have all had one thing in common: the roots of \(p(A)\) were all distinct. Solving advancement operator equations in which this is not the case is not much harder than what we've done so far, but we do need to treat it as a distinct case.

Example9.12

Find the general solution of the advancement operator equation \begin{equation*} (A-2)^2 f=0. \end{equation*}

Solution
Example9.13

Consider the recurrence equation \begin{equation*} f_{n+4} = -2f_{n+3} + 12f_{n+2} + -14 f_{n+1} + 5f_n \end{equation*} with initial conditions \(f_0 = 1\text{,}\) \(f_1= 2\text{,}\) \(f_2 = 4\text{,}\) and \(f_3 = 4\text{.}\) Find an explicit formula for \(f_n\text{.}\)

Solution

Subsection9.4.2Nonhomogeneous equations

As we mentioned earlier, nonhomogeneous equations are a bit trickier than solving homogeneous equations, and sometimes our first attempt at a solution will not be successful but will suggest a better function to try. Before we're done, we'll revisit the problem of lines in the plane that we've considered a couple of times, but let's start with a more illustrative example.

Example9.14

Consider the advancement operator equation \begin{equation*} (A+2)(A-6)f=3^n. \end{equation*} Let's try to find the general solution to this, since once we have that, we could find the specific solution corresponding to any given set of initial conditions.

When dealing with nonhomogeneous equations, we proceed in two steps. The reason for this will be made clear in Lemma 9.20, but let's focus on the method for the moment. Our first step is to find the general solution of the homogeneous equation corresponding to the given nonhomogeneous equation. In this case, the homogeneous equation we want to solve is \begin{equation*} (A+2)(A-6)f=0, \end{equation*} for which by now you should be quite comfortable in rattling off a general solution of \begin{equation*} f_1(n) = c_1 (-2)^n + c_2 6^n. \end{equation*}

Now for the process of actually dealing with the nonhomogeneity of the advancement operator equation. It actually suffices to find any solution of the nonhomogeneous equation, which we will call a particular solution. Once we have a particular solution \(f_0\) to the equation, the general solution is simply \(f=f_0 + f_1\text{,}\) where \(f_1\) is the general solution to the homogeneous equation.

Finding a particular solution \(f_0\) is a bit trickier than finding the general solution of the homogeneous equation. It's something for which you can develop an intuition by solving lots of problems, but even with a good intuition for what to try, you'll still likely find yourself having to try more than one thing on occasion in order to get a particular solution. What's the best starting point for this intuition? It turns out that the best thing to try is usually (and not terribly surprisingly) something that looks a lot like the right hand side of the equation, but we will want to include one or more new constants to help us actually get a solution. Thus, here we try \(f_0(n) = d 3^n\text{.}\) We have \begin{align*} (A+2)(A-6)f_0(n) \amp = (A+2)(d3^{n+1}-6d3^n)\\ \amp = (A+2)(-d3^{n+1})\\ \amp = -d3^{n+2} -2d3^{n+1}\\ \amp = -5d 3^{n+1}. \end{align*} We want \(f_0\) to be a solution to the nonhomogeneous equation, meaning that \((A+2)(A-6)f_0 = 3^n\text{.}\) This implies that we need to take \(d=-1/15\text{.}\) Now, as we mentioned earlier, the general solution is \begin{equation*} f(n) = f_0(n) + f_1(n) = -\frac{1}{15}3^n + c_1 (-2)^n + c_2 6^n. \end{equation*}

We leave it to you to verify that this does satisfy the given equation.

You hopefully noticed that in the previous example, we said that the first guess to try for a particular solution looks a lot like right hand side of the equation, rather than exactly like. Our next example will show why we can't always take something that matches exactly.

Example9.15

Find the solution to the advancement operator equation \begin{equation*} (A+2)(A-6)f=6^n \end{equation*} if \(f(0) = 1\) and \(f(1) = 5\text{.}\)

Solution

What's the lesson we should take away from this example? When making a guess at a particular solution of a nonhomogeneous advancement operator equation, it does us no good to use any terms that are also solutions of the corresponding homogeneous equation, as they will be annihilated by the advancement operator polynomial. Let's see how this comes into play when finally resolving one of our longstanding examples.

Example9.16

We're now ready to answer the question of how many regions are determined by \(n\) lines in the plane in general position as we discussed in Subsection 9.1.3. We have the recurrence equation \begin{equation*} r_{n+1} = r_n + n+1, \end{equation*} which yields the nonhomogeneous advancement operator equation \((A-1)r = n+1\text{.}\) As usual, we need to start with the general solution to the corresponding homogeneous equation. This solution is \(f_1(n) = c_1\text{.}\) Now our temptation is to try \(f_0(n)=d_1n+d_2\) as a particular solution. However since the constant term there is a solution to the homogeneous equation, we need a bit more. Let's try increasing the powers of \(n\) by \(1\text{,}\) giving \(f_0(n) = d_1n^2 + d_2n\text{.}\) Now we have \begin{align*} (A-1)(d_1n^2+d_2n) \amp = d_1(n+1)^2+d_2(n+1) - d_1n^2 -d_2n\\ \amp = 2d_1n+d_1+d_2. \end{align*} This tells us that we need \(d_1=1/2\) and \(d_2=1/2\text{,}\) giving \(f_0(n) = n^2/2 + n/2\text{.}\) The general solution is then \begin{equation*} f(n) = c_1 + \frac{n^2+n}{2}. \end{equation*}

What is our initial condition here? Well, one line divides the plane into two regions, so \(f(1) = 2\text{.}\) On the other hand, \(f(1) = c_1 + 1\text{,}\) so \(c_1=1\) and thus \begin{equation*} f(n) = 1 + \frac{n^2+n}{2} = \binom{n+1}{2} + 1 \end{equation*} is the number of regions into which the plane is divided by \(n\) lines in general position.

We conclude this section with one more example showing how to deal with a nonhomogeneous advancement operator equation in which the right hand side is of “mixed type”.

Example9.17

Give the general solution of the advancement operator equation \begin{equation*} (A-2)^2 f = 3^n + 2n. \end{equation*}

Solution