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
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
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
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.
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
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
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
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
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
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
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.
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
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
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
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
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
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:
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
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
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
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*}
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
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
