Skip to main content
Logo image

Section 4.4 Exponential Sequences

Subsection Section Preview

Investigate!
You have a large collection of 1×1 squares and 1×2 dominoes. You want to arrange these to make a 1×15 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 1×3 strips and 1×4 strips related to the 1×5 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:
0,1,1,2,3,5,8,13,21,34,55,.
If we look at the first differences, we get this sequence:
1,1,2,3,5,8,13,21,34,,
which is the Fibonacci sequence itself. This is not surprising, since the Fibonacci sequence is defined by the recurrence relation Fn=Fn1+Fn2. 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 nth differences will be constant.
Another sequence that has this behavior is the powers of 2:
1,2,4,8,16,32,64,128,256,512,
which has differences
1,2,4,8,16,32,64,128,256,.
We can also see this from the recurrence relation, since
an=2an1=an1+an1.
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.
Consider the recurrence relation
an=5an16an2.
Since the nth term is given as a combination of the two previous terms, we will need two initial terms to determine the sequence. Different initial terms will give different sequences.
(a)
What sequence do you get if the initial conditions are a0=1, a1=2? Give the first five terms (including 1 and 2).
(b)
Based on the first few terms, what is a closed formula for this sequence?
an=
(c)
What sequence do you get if the initial conditions are a0=1, a1=3? Give the first five terms.
(d)
Based on the first few terms, what is a closed formula for this sequence?
an=
(e)
What sequence do you get if the initial conditions are a0=2, a1=5? Give the first five terms.
(f)
Based on the first few terms, what is a closed formula for this sequence?
an=
Hint.
How do the terms in this sequence relate to the terms in the previous two sequences?

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 1,1+2,1+2+4,1+2+4+8, that gives
1,3,7,15,31,63,
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 2,4,8,16,32,64,, so we might guess that the closed formula for the sequence of sums is 2n+11. If this is correct, then the answer to the candy question would be 2111=2047.
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.

What is 3+6+12+24++12288?
Solution.
Multiply each term by 2, the common ratio. We get 2S=6+12+24++24576. Now subtract: 2SS=3+24576=24573. Since 2SS=S, we have our answer.
To better see what happened in the above example, we can write it this way:
S= 3+ 6+12+24++12288
2S= 6+12+24++12288 +24576
S= 3+ 0+0+0++0 24576
Then divide both sides by 1 and we have the same result for S. 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 S(n)=2+10+50++25n.
Solution.
The common ratio is 5. So we have
S =2+10+50++25n
5S =      10+50++25n+25n+1
4S =225n+1
Thus S=225n+14
Even though this might seem like a new technique, you have probably used it before.

Example 4.4.3.

Express 0.464646 as a fraction.
Solution.
Let N=0.46464646. Consider 0.01N. We get:
N= 0.4646464
0.01N= 0.00464646
0.99N= 0.46
So N=4699. What have we done? We viewed the repeating decimal 0.464646 as a sum of the geometric sequence 0.46,0.0046,0.000046, The common ratio is 0.01. 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 an that has a rate of growth that is an exponential function: anan1=bn, where bn 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 an=an1+6an2. In other words, we want to find a function of n which satisfies anan16an2=0. Think about how we build up this sequence iteratively.
a2=a1+6a0a3=a2+6a1=a1+6a0+6a1a4=a3+6a2=a1+6a0+6a1+62a0+62a1
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 6 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 rn for some constant r.
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 rn into the recursion above? We get
rnrn16rn2=0.
Now solve for r:
rn2(r2r6)=0,
so by factoring, r=2 or r=3 (or r=0, although this does not help us). This tells us that an=(2)n is a solution to the recurrence relation, as is an=3n. Which one is correct? They both are, unless we specify initial conditions. Notice we could also have an=(2)n+3n. Or an=7(2)n+43n. In fact, for any a and b, an=a(2)n+b3n is a solution (try plugging this into the recurrence relation). To find the values of a and b, 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 rn2 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 an+αan1+βan2=0, the characteristic polynomial is
x2+αx+β
giving the characteristic equation:
x2+αx+β=0.
If r1 and r2 are two distinct roots of the characteristic polynomial (i.e., solutions to the characteristic equation), then the solution to the recurrence relation is
an=ar1n+br2n,
where a and b are constants determined by the initial conditions.

Example 4.4.4.

Solve the recurrence relation an=7an110an2 with a0=2 and a1=3.
Solution.
Rewrite the recurrence relation an7an1+10an2=0. Now form the characteristic equation:
x27x+10=0
and solve for x:
(x2)(x5)=0,
so x=2 and x=5 are the characteristic roots. We therefore know that the solution to the recurrence relation will have the form
an=a2n+b5n.
To find a and b, plug in n=0 and n=1 to get a system of two equations with two unknowns:
2=a20+b50=a+b3=a21+b51=2a+5b.
Solving this system gives a=73 and b=13, so the solution to the recurrence relation is
an=732n135n.
Perhaps the most famous recurrence relation is Fn=Fn1+Fn2, which together with the initial conditions F0=0 and F1=1 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 (xr)2. It is still the case that rn 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 an=ar1n+br2n, since we can’t distinguish between r1n and r2n. We are in luck though:

Characteristic Root Technique for Repeated Roots.

Suppose the recurrence relation an=αan1+βan2 has a characteristic polynomial with only one root r. Then the solution to the recurrence relation is
an=arn+bnrn
where a and b are constants determined by the initial conditions.
Notice the extra n in bnrn. This allows us to solve for the constants a and b from the initial conditions.

Example 4.4.5.

Solve the recurrence relation an=6an19an2 with initial conditions a0=1 and a1=4.
Solution.
The characteristic polynomial is x26x+9. We solve the characteristic equation
x26x+9=0
by factoring:
(x3)2=0,
so x=3 is the only characteristic root. Therefore we know that the solution to the recurrence relation has the form
an=a3n+bn3n
for some constants a and b. Now use the initial conditions:
a0=1=a30+b030=aa1=4=a3+b13=3a+3b.
Since a=1, we find that b=13. Therefore the solution to the recurrence relation is
an=3n+13n3n.
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, an=2an1+an23an3 has characteristic polynomial x32x2x+3. 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 an=ar1n+br2n+cr3n 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: an 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 aj terms. For example, an=2an1+1 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.

Reading Questions Reading Questions

1.

Which of the following recurrence relations would be good candidates to try the characteristic root technique on? Select all that apply
  • an=3an1+an2
  • Correct: an is written in terms of only multiple of previous terms.
  • an=an1+2an2+3an3
  • This works too, although the characteristic polynomial will have degree 3, so finding characteristic roots will be difficult.
  • an=132n+23(1)n
  • This looks like it is the closed formula that would result from a characteristic root technique application, but isn’t a recursive formula.
  • an=an1+3an2+5
  • The addition of the constant makes it so we cannot use the characteristic root technique directly. While there are methods for dealing with this, we have not considered them in this section.
  • x23x1=0
  • This might be a characteristic polynomial (in fact, it is for the sequence given by an=3an1+an), but it is not a recursive definition itself.

2.

At what step do you need to refer to the initial conditions when completing the characteristic root technique? What would happen if you didn’t use these? Explain.

3.

What questions do you have? Write at least one question about the content of this section that you or a classmate might be curious about.

Exercises Practice Problems

1.

Find 3+6+12++3218.

2.

Find 135+925+(1)27327527.

3.

Solve the recurrence relation an=an1+2n with a0=3.
an=
Hint.
Use telescoping or iteration.

4.

Find the solution to the recurrence relation an=3an1+10an2 with initial terms a0=2 and a1=3.
an=

5.

Find the solution to the recurrence relation an=an1+12an2 with initial terms a0=2 and a1=1.
an=
Find the solution to the recurrence relation bn=bn1+12bn2 with initial terms b0=5 and b1=10.
bn=

6.

Find the solution to the recurrence relation an=an1+6an2 with initial terms a0=1 and a1=16.
an=

Exercises Additional Exercises

1.

Find the next two terms in (an)n0 beginning 3,5,11,21,43,85. Then give a recursive definition for the sequence. Finally, use the characteristic root technique to find a closed formula for the sequence.

2.

Consider the sequences 2,5,12,29,70,169,408, (with a0=2).
  1. Describe the rate of growth of this sequence.
  2. Find a recursive definition for the sequence.
  3. Find a closed formula for the sequence.
  4. If you look at the sequence of differences between terms, and then the sequence of second differences, the sequence of third differences, and so on, will you ever get a constant sequence? Explain how you know.

3.

Show that 4n is a solution to the recurrence relation an=3an1+4an2.

4.

Suppose that rn and qn are both solutions to a recurrence relation of the form an=αan1+βan2. Prove that crn+dqn is also a solution to the recurrence relation, for any constants c,d.

5.

Think back to the magical candy machine at your neighborhood grocery store. Suppose that the first time a quarter is put into the machine 1 Skittle comes out. The second time, 4 Skittles, the third time 16 Skittles, the fourth time 64 Skittles, etc.
  1. Find both a recursive and closed formula for how many Skittles the nth customer gets.
  2. Check your solution for the closed formula by solving the recurrence relation using the characteristic root technique.

6.

Let an be the number of 1×n tile designs you can make using 1×1 squares available in 4 colors and 1×2 dominoes available in 5 colors.
  1. First, find a recurrence relation to describe the problem. Explain why the recurrence relation is correct (in the context of the problem).
  2. Write out the first 6 terms of the sequence a1,a2,.
  3. Solve the recurrence relation. That is, find a closed formula for an.

7.

You have access to 1×1 tiles which come in 2 different colors and 1×2 tiles which come in 3 different colors. We want to figure out how many different 1×n path designs we can make out of these tiles.
  1. Find a recursive definition for the sequence an of paths of length n.
  2. Solve the recurrence relation using the characteristic root technique.

8.

Solve the recurrence relation an=2an1an2.
  1. What is the solution if the initial terms are a0=1 and a1=2?
  2. What do the initial terms need to be in order for a9=30?
  3. For which x are there initial terms which make a9=x?

9.

Consider the recurrence relation an=4an14an2.
  1. Find the general solution to the recurrence relation (beware the repeated root).
  2. Find the solution when a0=1 and a1=2.
  3. Find the solution when a0=1 and a1=8.

10.

Here is a surprising use of sequences to answer a counting question: How many license plates consist of 6 symbols, using only the three numerals 1, 2, and 3 and the four letters a, b, c, and d, so that no numeral appears after any letter? For example, “31ddac”, “123321”, and “ababab” are each acceptable license plates, but “13ba2c” is not.
  1. First answer this question by considering different cases: how many of the license plates contain no numerals? How many contain one numeral, etc.
  2. Now use the techniques of this section to show why the answer is 4737.
You have attempted 1 of 11 activities on this page.