Subsection Section Preview
Investigate!
You have a large collection of
squares and
dominoes. You want to arrange these to make a
strip. How many ways can you do this?
What if the squares come in three different colors and the dominos come in four different colors? And why is this second question easier than the first?
Hint.
Start by creating a recurrence relation. How are the different
strips and
strips related to the
strips?
In
Section 4.3 we saw that if a sequence has some sequence of differences that is constant, then the sequence has a polynomial closed formula. Are there sequences that never have constant differences? And what would their closed formulas look like?
Consider the Fibonacci sequence:
If we look at the first differences, we get this sequence:
which is the Fibonacci sequence itself. This is not surprising, since the Fibonacci sequence is defined by the recurrence relation That is saying precisely that to get the next turn of the sequence, we take the current term and add... a term in the sequence!
Of course, if we take another difference, we will get the same sequence back, and again and again, so no
th differences will be constant.
Another sequence that has this behavior is the powers of 2:
which has differences
We can also see this from the recurrence relation, since
The rate of growth for this, and in fact any geometric sequence, is the sequence itself.
If you have studied calculus, you may recall that the functions that have themselves (or close) as their rate of change (derivative, in the calculus context) are exactly the exponential functions. Here too, geometric sequences, which have exponential closed formulas, have themselves as their rate of change.
In this section, we will explore sequences that are changing at a rate proportional to the sequence itself, and see how these all have an exponential closed formula, or some variation of that.
Worksheet Preview Activity
1.
Subsection Summing Geometric Sequences: Multiply, Shift, and Subtract
Suppose a candy machine dispenses candy in a geometric sequence by first giving 1 candy, then 2 candies, then 4, then 8, and so on. How many candies will you have received in total after 10 turns of the machine?
We can create the sequence of partials sum as that gives
This is not a geometric sequence, but is almost. In fact, if we add 1 to each term, we get what sure looks like the geometric sequence so we might guess that the closed formula for the sequence of sums is If this is correct, then the answer to the candy question would be
More intriguing though is the observation that the sequence of partial sums of a geometric sequence is again geometric-ish. Let’s consider how to find the sum of a geometric sequence in general.
We cannot just reverse and add as we did for the sum of an arithmetic sequence. Do you see why? The reason we got the same term added to itself many times is because there was a constant difference. So as we added that difference in one direction, we subtracted the difference going the other way, leaving a constant total. For geometric sums; we have a different technique.
Example 4.4.1.
Solution.
Multiply each term by 2, the common ratio. We get
Now subtract:
Since
we have our answer.
To better see what happened in the above example, we can write it this way:
Then divide both sides by
and we have the same result for
The idea is, by multiplying the sum by the common ratio, each term becomes the next term. We shift over the sum to get the subtraction to mostly cancel out, leaving just the first term and the new last term.
Example 4.4.2.
Find a closed formula for
Solution.
The common ratio is 5. So we have
Even though this might seem like a new technique, you have probably used it before.
Example 4.4.3.
Solution.
So
What have we done? We viewed the repeating decimal
as a sum of the geometric sequence
The common ratio is
The only real difference is that we are now computing an
infinite geometric sum, we do not have the extra “last” term to consider. Really, this is the result of taking a limit as we would in calculus when we compute
infinite geometric sums.
To summarize, we now can find a closed formula for a sequence
that has a rate of growth that is an exponential function:
where
is a geometric sequence (i.e., an exponential function). What sort of closed formula do we get here? It’s
another exponential function!
Subsection The Characteristic Root Technique
Suppose we want to solve a recurrence relation expressed as a combination of the two previous terms, such as In other words, we want to find a function of which satisfies Think about how we build up this sequence iteratively.
Let’s stop there and agree this is getting very complicated. However, we do notice that in each step, we would, among other things, multiply a previous iteration by 6. So our closed formula would include multiplied some number of times. Thus it is reasonable to guess the solution will contain parts that look geometric. Perhaps the solution will take the form for some constant
The nice thing is, we know how to check whether a formula is actually a solution to a recurrence relation: plug it in. What happens if we plug in into the recursion above? We get
Now solve for
so by factoring, or (or although this does not help us). This tells us that is a solution to the recurrence relation, as is Which one is correct? They both are, unless we specify initial conditions. Notice we could also have Or In fact, for any and is a solution (try plugging this into the recurrence relation). To find the values of and use the initial conditions.
This points us in the direction of a more general technique for solving recurrence relations. Notice we will always be able to factor out the
as we did above. So we really only care about the other part. We call this other part the
characteristic equation for the recurrence relation. We are interested in finding the roots of the characteristic equation, which are called (surprise) the
characteristic roots.
Characteristic Roots.
Given a recurrence relation the characteristic polynomial is
giving the characteristic equation:
If and are two distinct roots of the characteristic polynomial (i.e., solutions to the characteristic equation), then the solution to the recurrence relation is
where and are constants determined by the initial conditions.
Example 4.4.4.
Solve the recurrence relation
with
and
Solution.
Rewrite the recurrence relation Now form the characteristic equation:
and solve for
so and are the characteristic roots. We therefore know that the solution to the recurrence relation will have the form
To find and plug in and to get a system of two equations with two unknowns:
Solving this system gives and so the solution to the recurrence relation is
Perhaps the most famous recurrence relation is
which together with the initial conditions
and
defines the Fibonacci sequence. But notice that this is precisely the type of recurrence relation on which we can use the characteristic root technique. When we do, the only thing that changes is that the characteristic equation does not factor, so we must use the quadratic formula to find the characteristic roots. In fact, doing so gives the third most famous irrational number,
the
golden ratio.
Before leaving the characteristic root technique, we should think about what might happen when solving the characteristic equation. We have an example above in which the characteristic polynomial has two distinct roots. These roots can be integers, or perhaps irrational numbers (requiring the quadratic formula to find them). In these cases, we know what the solution to the recurrence relation looks like.
However, it is possible for the characteristic polynomial to have only one root. This can happen if the characteristic polynomial factors as
It is still the case that
would be a solution to the recurrence relation, but we won’t be able to find solutions for all initial conditions using the general form
since we can’t distinguish between
and
We are in luck though:
Characteristic Root Technique for Repeated Roots.
Suppose the recurrence relation has a characteristic polynomial with only one root Then the solution to the recurrence relation is
where and are constants determined by the initial conditions.
Notice the extra
in
This allows us to solve for the constants
and
from the initial conditions.
Example 4.4.5.
Solve the recurrence relation
with initial conditions
and
Solution.
The characteristic polynomial is We solve the characteristic equation
by factoring:
so is the only characteristic root. Therefore we know that the solution to the recurrence relation has the form
for some constants and Now use the initial conditions:
Since we find that Therefore the solution to the recurrence relation is
Although we will not consider examples more complicated than these, this characteristic root technique can be applied to much more complicated recurrence relations. For example,
has characteristic polynomial
Assuming we see how to factor such a degree 3 (or more) polynomial, we can easily find the characteristic roots and as such solve the recurrence relation (the solution would look like
if there were 3 distinct roots). It is also possible that the characteristic roots are complex numbers.
However, the characteristic root technique is only useful for solving recurrence relations in a particular form:
is given as a linear combination of some number of previous terms. These recurrence relations are called
linear homogeneous recurrence relations with constant coefficients. The “homogeneous” refers to the fact that there is no additional term in the recurrence relation other than a multiple of
terms. For example,
is
non-homogeneous because of the additional constant 1. There are general methods of solving such things, but we will not consider them here, other than through the use of telescoping or iteration described above.