AC Solving advancement operator equations

Section 9.4 Solving 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.

Subsection 9.4.1 Homogeneous 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.

Example 9.9.

Find all solutions to the advancement operator equation

\begin{equation} (A^2+A-6)f = 0.\tag{9.4.1} \end{equation}

Solution.

Before focusing on finding all solutions as we’ve been asked to do, let’s just try to find some solution. We start by noticing that here \(p(A) = A^2+A-6 = (A+3)(A-2)\text{.}\) With \(p(A)\) factored like this, we realize that we’ve already solved part of this problem in Example 9.8! In that example, the polynomial of \(A\) we encountered was (while not explicitly stated as such there) \(A-2\text{.}\) The solutions to \((A-2)f_1=0\) are of the form \(f_1(n) = c_12^n\text{.}\) What happens if we try such a function here? We have

\begin{equation*} (A+3)(A-2)f_1(n) = (A+3)0 = 0, \end{equation*}

so that \(f_1\) is a solution to our given advancement operator equation. Of course, it can’t be all of them. However, it’s not hard to see now that \((A+3)f_2 = 0\) has as a solution \(f_2(n) = c_2(-3)^n\) by the same reasoning that we used in Example 9.8. Since \((A+3)(A-2) = (A-2)(A+3)\text{,}\) we see right away that \(f_2\) is also a solution of (9.4.1).

Now we’ve got two infinite families of solutions to (9.4.1). Do they give us all the solutions? It turns out that by combining them, they do in fact give all of the solutions. Consider what happens if we take \(f(n) = c_1 2^n + c_2 (-3)^n\) and apply \(p(A)\) to it. We have

\begin{align*} (A+3)(A-2)f(n) \amp = (A+3)(c_1 2^{n+1} + c_2 (-3)^{n+1} - 2(c_12^n + c_2(-3)^n))\\ \amp = (A+3)(-5c_2(-3)^{n})\\ \amp = -5c_2(-3)^{n+1}-15c_2(-3)^n\\ \amp = 15c_2(-3)^n - 15c_2(-3)^n\\ \amp =0. \end{align*}

It’s not all that hard to see that since \(f\) gives a two-parameter family of solutions to (9.4.1), it gives us all the solutions, as we will show in detail in Section 9.5.

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.

Example 9.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.\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! You can mimic the verification we used in the previous example to see that this does satisfy (9.4.2). If that feels tedious, consider how you would use the binomial theorem to expand the terms in this expression for \(t(n)\text{.}\) With appropriate values for \(c_1\) and \(c_2\text{,}\) it seems plausible that we could get rid of the square roots and fractions. 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*}

Example 9.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 shouldn’t be surprised that we immediately make use of the roots of \(p(A)\) and have that the solution is

\begin{equation*} f(n) = c_1(-1)^n + c_2 6^n + c_3 (-4)^n. \end{equation*}

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.

Example 9.12.

Find the general solution of the advancement operator equation

\begin{equation*} (A-2)^2 f=0. \end{equation*}

Solution.

Here we have the repeated root problem that we mentioned a moment ago. We see immediately that \(f_1(n) = c_12^n\) is a solution to this equation, but that can’t be all, as we mentioned earlier that we must have a \(2\)-parameter family of solutions to such an equation. You might be tempted to try \(f_2(n) = c_2 2^n\) and \(f(n) = f_1(n) + f_2(n)\text{,}\) but then this is just \((c_1+c_2)2^n\text{,}\) which is really just a single parameter, \(c=c_1+c_2\text{.}\)

What can we do to resolve this conundrum? What if we tried \(f_2(n) = c_2 n2^n\text{?}\) Again, if you’re familiar with differential equations, this would be the analogous thing to try, so let’s give it a shot. Let’s apply \((A-2)^2\) to this \(f_2\text{.}\) We have

\begin{align*} (A-2)^2 f_2(n) \amp = (A-2)(c_2(n+1)2^{n+1} - 2c_2 n2^n)\\ \amp = (A-2)(c_2 2^{n+1})\\ \amp = c_22^{n+2} - 2c_2 2^{n+1}\\ \amp = 0. \end{align*}

Since \(f_2\) satisfies our advancement operator equation, we have that the general solution is

\begin{equation*} f(n) = c_1 2^n + c_2 n2^n. \end{equation*}

Example 9.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.

We again start by writing the given recurrence equation as an advancement operator equation for a function \(f(n)\text{:}\)

\begin{equation} (A^4 +2A^3 -12A^2+14A-5)f = 0.\tag{9.4.3} \end{equation}

Factoring \(p(A) = A^4 +2A^3 -12A^2+14A-5\) gives \(p(A) = (A+5)(A-1)^3\text{.}\) Right away, we see that \(f_1(n) = c_1 (-5)^n\) is a solution. The previous example should have you convinced that \(f_2(n) = c_2\cdot 1^n = c_2\) and \(f_3(n) = c_3 n \cdot 1^n = c_3 n\) are also solutions, and it’s not likely to surprise you when we suggest trying \(f_4(n) = c_4 n^2\) as another solution. To verify that it works, we see

\begin{align*} (A+5)(A-1)^3 f_4(n) \amp = (A+5)(A-1)^2(c_4(n+1)^2 - c_4 n^2)\\ \amp = (A+5)(A-1)^2 (2c_4 n + c_4)\\ \amp = (A+5)(A-1)(2c_4(n+1) + c_4 - 2c_4 n -c_4)\\ \amp = (A+5)(A-1)(2c_4)\\ \amp = (A+5)(2c_4-2c_4)\\ \amp = 0. \end{align*}

Thus, the general solution is

\begin{equation*} f(n) = c_1 (-5)^n + c_2 + c_3 n + c_4n^2. \end{equation*}

Since we have initial conditions, we see that

\begin{align*} 1= f(0) \amp = c_1+c_2\\ 2 = f(1) \amp = -5c_1 + c_2 + c_3 + c_4\\ 4 = f(2) \amp = 25c_1 + c_2 + 2c_3 + 4c_4\\ 4 = f(3) \amp = -125c_1 + c_2 +3c_3 +9c_4 \end{align*}

is a system of equations whose solution gives the values for the \(c_i\text{.}\) Solving this system gives that the desired solution is

\begin{equation*} f(n) = \frac{1}{72} (-5)^n +\frac{71}{72} + \frac{5}{6} n +\frac{1}{4} n^2. \end{equation*}

Subsection 9.4.2 Nonhomogeneous 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.

Example 9.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.

Example 9.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.

The corresponding homogeneous equation here is the same as in the previous example, so its general solution is again \(f_1(n) = c_1(-2)^n + c_2 6^n\text{.}\) Thus, the real work here is finding a particular solution \(f_0\) to the given advancement operator equation. Let’s just try what our work on the previous example would suggest here, namely \(f_0(n) = d6^n\text{.}\) Applying the advancement operator polynomial \((A+2)(A-6)\) to \(f_0\) then gives, uh, well, zero, since \((A-6)(d6^n) = d6^{n+1}-6d6^n =0\text{.}\) Huh, that didn’t work out so well. However, we can take a cue from how we tackled homogeneous advancement operator equations with repeated roots and introduce a factor of \(n\text{.}\) Let’s try \(f_0(n) = dn6^n\text{.}\) Now we have

\begin{align*} (A+2)(A-6)(dn6^n) \amp = (A+2)(d(n+1)6^{n+1}-6dn6^n)\\ \amp = (A+2)d6^{n+1}\\ \amp = d6^{n+2} + 2d 6^{n+1}\\ \amp = 6^n(36d+12d) = 48d6^n. \end{align*}

We want this to be equal to \(6^n\text{,}\) so we have \(d = 1/48\text{.}\) Therefore, the general solution is

\begin{equation*} f(n) = \frac{1}{48}n6^n + c_1 (-2)^n + c_2 6^n. \end{equation*}

All that remains is to use our initial conditions to find the constants \(c_1\) and \(c_2\text{.}\) We have that they satisfy the following pair of equations:

\begin{align*} 1 \amp = c_1 + c_2\\ 5 \amp = \frac{1}{8} -2c_1+6c_2 \end{align*}

Solving these, we arrive at the desired solution, which is

\begin{equation*} f(n) = \frac{1}{48}n6^n + \frac{9}{64} (-2)^n + \frac{55}{64} 6^n. \end{equation*}

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.

Example 9.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”.

Example 9.17.

Give the general solution of the advancement operator equation

\begin{equation*} (A-2)^2 f = 3^n + 2n. \end{equation*}

Solution.

Finding the solution to the corresponding homogeneous equation is getting pretty easy at this point, so just note that

\begin{equation*} f_1(n) = c_1 2^n + c_2 n2^n. \end{equation*}

What should we try as a particular solution? Fortunately, we have no interference from \(p(A)=(A-2)^2\) here. Our first instinct is probably to try \(f_0(n) = d_1 3^n + d_2 n\text{.}\) However, this won’t actually work. (Try it. You wind up with a leftover constant term that you can’t just make zero.) The key here is that if we use a term with a nonzero power of \(n\) in it, we need to include the lower order powers as well (so long as they’re not superfluous because of \(p(A)\)). Thus, we try

\begin{equation*} f_0(n) = d_1 3^n + d_2 n + d_3. \end{equation*}

This gives

\begin{align*} (A-2)^2(d_1 3^n + d_2 n + d_3) \amp = (A-2)(d_13^{n+1} + d_2(n+1)+d_3 - 2d_1 3^n - 2d_2 n -2d_3)\\ \amp = (A-2)(d_13^n - d_2n + d_2 -d_3)\\ \amp = d_1 3^{n+1} - d_2(n+1) + d_2 - d_3 - 2 d_1 3^n + 2d_2 n -2d_2 + 2d_3\\ \amp = d_1 3^n + d_2 n -2d_2 + d_3. \end{align*}

We want this to be \(3^n+2n\text{,}\) so matching coefficients gives \(d_1 = 1\text{,}\) \(d_2 =2\text{,}\) and \(d_3=4\text{.}\) Thus, the general solution is

\begin{equation*} f(n) = 3^n+2n+4 + c_1 2^n + c_2 n 2^n. \end{equation*}

Reading Questions 9.4.3 Reading Questions

1.

Solve the advancement operator equation \((A+4)f(n) = 0\) with the initial condition \(f(0)=2\text{.}\) In the box below, type your answer in the form \(f(n) = \text{blah}\) and briefly explain in couple of sentences how you arrived at this solution.

2.

Let \(c_1\) and \(c_2\) be constants and define \(f(n) = c_1 3^n + c_2 (-4)^n\text{.}\) Compute

\begin{equation*} (A+4)(A-3)f(n) \end{equation*}

in two steps: First, compute \((A-3)f(n)\) and in the box below tell me what you get for this first step after simplifying. (Please do not put all your work in the box!) Second, take your answer from the first step and apply \((A-4)\) to it. In the box below, tell me what you get for this second step after simplifying.

You have attempted of activities on this page.

Prev Top Next