Chapter 1

Recursive Sequences

We have described a sequence in at least two different ways:

 a list of real numbers where there is a first number, a second number, and so on. We
are interested in infinite sequences, so our lists do not end. Examples are f1; 2; 3; 4; 5; 6; : : :g
or f2; 4; 8; 8; 8; 8; 8; 8; 16; : : :g. The sequences we saw in the last section we were usu-
ally able to describe by some formula. This is not always the case.

 a function a W N ! R where we denoted the output by a.n/ D an . One example would

be an D n. Others are an D 2n , an D 1=n. Any function that is defined on the set of
whole numbers gives us a sequence.

There is yet another way to describe a sequence. This process is known as recursion.
Recursion is the process of choosing a starting term and repeatedly applying the same
process to each term to arrive at the following term. Recursion requires that you know the
value of the term or terms immediately before the term you are trying to find.
A recursive formula always has two parts:

1. the starting value for the first term a0 ;

2. the recursion equation for an as a function of an 1 (the term before it.)

Example 1.1. Consider the sequence given by an D 2an 1 C 1 with a0 D 4. The recursion
function (or recursion equation) tells us how to find a1 , a2 , and so on.

a1 D 2a1 C 1 D 2.4/ C 1 D 9
a2 D 2a1 C 1 D 2.9/ C 1 D 19
a3 D 2a2 C 1 D 2.19/ C 1 D 39

What is a10 ? Here the problem is that we have to find a9 in order to find a10 , but to find
a9 we need a8 , but to find a8 we need a7 , and so on.

Example 1.2. [Fibonacci sequence] Consider the following recursion equation.

Fn D Fn 1 C Fn 2; F0 D 1; F1 D 1:

1
2 CHAPTER 1. RECURSIVE SEQUENCES

F2 D F1 C F0 D 2
F3 D F2 C F1 D 3
In fact, it is easier to list these out in a list by just adding the previous two terms to get the
next term.
f1; 1; 2; 3; 5; 8; 13; 21; 34; 55; 89; 144; 233; 377; 610; 987; 1597; : : : g
The Fibonacci sequence has a long history in mathematics and you can find out more
about it online at any number of websites. The Fibonacci sequence is named after the
13th-century Italian mathematician known as Fibonacci, who used it to solve a problem
concerning the breeding of rabbits. This sequence also occurs in numerous applications in
plant biology.
Example 1.3. 1. Write recursive equations for the sequence f5; 7; 9; 11; : : :g.
2. Write recursive equations for the sequence f2; 4; 8; 16; : : :g.
3. Write recursive equations for the sequence f1; 2; 6; 24; 120; 720; : : :g.
4. Write recursive equations for the sequence f2; 3; 6; 18; 108; 1944; 209952; : : :g
Exercises
1. What is the 5th term of the recursive sequence defined as follows: a1 D 5, an D
3an 1 ?
2. What is the 5th term of the recursive sequence defined as follows: a1 D 2, an D
2an 1 1?
3. What is the 1st term of a recursive sequence in which an D 4an 1, if a4 D 192?
4. Write recursive equations for the sequence f5; 11; 17; 23; : : :g.
5. Write recursive equations for the sequence f3; 6; 12; 24; : : :g.
6. Write recursive equations for the sequence f2; 4; 16; 256; 65536; : : :g.
7. Write recursive equations for the sequence f2; 6; 14; 30; 62; : : :g.
8. Write recursive equations for the sequence f3; 4; 7; 11; 18; 29; : : :g.
9. Write recursive equations for the sequence f6561; 81; 9; 3; : : :g.
10. Write the first five terms of the sequence in which a1 D 1 and an D 2an 1 2.
11. Write the first five terms of the sequence in which a1 D 2 and an D 5an 1 5.
Example 1.4. [Depreciation] Consider a situation in which the value of a car depreciates
10% per year. If the car is originally valued at $36,000, the following year it is worth 90%
of $36,000, or $32,400. After another year, the value is 90% of $32,400, or $29,160. If we
write the decreasing values as a list: 36,000, 32,400, 29,160. . . we have written a sequence
- a sequence where each term depends on the value of the preceding term - a recursive
sequence: an D 0:9an 1 with a0 D 36000.

MA 114 ©UK Mathematics Department

1.1. LIMITS OF RECURSIVE SEQUENCES 3

Two simple examples of recursive definitions are for arithmetic sequences and geomet-
ric sequences. An arithmetic sequence has a common difference, or a constant difference
between each term.

an D an 1 Cd or an an 1 D d:

The common difference, d , is analogous to the slope of a line. In this case it is possible to
find a formula for the nth term directly. This simplifies finding say the 42nd term.
A geometric sequence has a common ratio.

an
an D r
an 1 or D r:
an 1

Again, in this case it is relatively easy to find a formula for the nth term: an D a0 r n .
Thus, there are sequences that can be defined recursively, analytically, and those that can
be defined in both manners.
Recursive sequences are sometimes called a difference equations. The recursive se-
quence in Example 1 is called a first-order difference equation because an depends on
just the preceding term an 1 , whereas the Fibonacci sequence is a second-order difference
equation because Fn depends on the two preceding terms Fn 1 and Fn 2 . The general
first-order difference equation is of the form anC1 D f .an / where f is some function.
Why is it called a difference equation? The word difference comes from the fact that such
equations are often formulated in terms of the difference between one term and the next:
an D anC1 an . The equation an D g.an / can be written as follows:

anC1 an D g.an /
anC1 D an C g.an / D f .an /

where f .x/ D x C g.x/.

1.1 Limits of Recursive Sequences

In our previous discussion, we learned how to find lim an when an is given explicitly as
n!1
a function of n. How do you find such a limit when an is defined recursively.
When we define a first-order sequence fan g recursively, we express anC1 in terms of
an and specify a value for a1 . We can then compute successive values of an , which might
allow us to guess the limit if it exists. In some cases (as in the next example), we can find a
solution of the recursion and then determine the limit (if it exists).

1 3
Example 1.5. Compute an for n D 1; 2; : : : ; 6 when anC1 D 4 an C 4 with a1 D 2. Find a

MA 114 ©UK Mathematics Department

4 CHAPTER 1. RECURSIVE SEQUENCES

solution of the recursion, and then take a guess at the limiting behavior of the sequence.

a1 D 2
1 3 5
a2 D a1 C D D 1:25
4 4 4
1 3 17
a3 D a2 C D D 1:0625
4 4 16
1 3 65
a4 D a3 C D D 1:015625
4 4 64
1 3 257
a5 D a4 C D D 1:00390625
4 4 256
1 3 1025
a6 D a5 C D D 1:0009765625
4 4 1024

There seems to be a pattern, namely, that the denominators are powers of 4 and the
4n 1 C 1
numerators are just 1 larger than the denominators. We will try an D and check
4n 1
whether this is indeed a solution of the recursion.
First, we need to check the initial condition: a1 D .40 C 1/=40 D 2=1 D 2. This agrees
with the given initial condition. Next, we need to check whether an satisfies the recursion.
Accordingly, we write

4n C 1
 
1 1 1 1
anC1 D n
D1C
n 1
D1C
4 4 4 4 4n 1
4n 1 C 1 1 1
an D n 1
) an D 1 C n 1 ) n 1 D an 1
4 4 4
1 1 1 1 3
anC1 D 1 C n 1
D 1 C .an 1/ D an C
44 4 4 4
which is the given recursion. We can now use our formula to find the limit. We have

4n 1 C 1
 
1
lim an D lim D lim 1 C D 1:
n!1 n!1 4n 1 n!1 4n 1

1
since lim D 0.
n!1 4n 1

Finding an explicit expression for an as in the above example is often not possible,
because solving recursions can be very difficult or even impossible. How, then, can we say
anything about the limiting behavior of a recursively defined sequence?
The following procedure will allow us to identify candidates for limits: A fixed point of
a function is a point x so that f .x/ D x. For recursive sequences this translates as if the
sequence fan g is can be given as anC1 D f .an / and if a is a fixed point for f .x/, then if
an D a is equal to the fixed point for some k, then all successive values of an are also equal
to a for k > n.

MA 114 ©UK Mathematics Department

1.1. LIMITS OF RECURSIVE SEQUENCES 5

Now,if anC1 D g.an /,then if a1 D a and a is a fixed point, it follows that a2 D g.a1 / D
g.a/ D a, a3 D g.a2 / D g.a/ D a, and so on. That is, a fixed point satisfies the equation

a D g.a/:

We will use this representation to find fixed points.

In the previous example, we had the recursion anC1 D 14 an C 34 . Fixed points for the
recursion thus would satisfy a D 14 a C 34 . Solve this equation for a.

1 3
aD aC
4 4
3 3
aD
4 4
aD1

We find that a D 1. In the above example this fixed point is also the limiting value of the
sequence. This will not always be the case: A fixed point is only a candidate for a limit;
a sequence does not have to converge to a given fixed point (unless a0 is already equal
to the fixed point). The next two examples illustrate convergence and non-convergence,
respectively.

Example 1.6. Assume that lim an exists for

n!1
p
anC1 D 3an with a0 D 2:

Find lim an .
n!1
Since the problem tells us that the limit exists, we don’t have to worry about existence.
We may assume that lim an D A. The problem that remains is to identify the limit. To do
n!1
this we need to note that if lim an D A then it is true that lim anC1 D A, since these are
n!1 n!1
exactly the same sequence. Now, we compute the fixed points. We solve
p
lim anC1 D lim 3an
n!1 n!1
p
A D 3A

This has two solutions, namely, A D 0 and A D 3. When a0 D 2, we have an > 2 for
all n D 1; 2; 3; : : :, so we can exclude A D 0 as the limiting value. This leaves only one
possibility, and we conclude that
lim an D 3:
n!1

Consider some successive values of an , which we collect in the following table (accurate to
two decimals):
n 0 1 2 3 4 5 6 7
an 2 2.45 2.71 2.85 2.92 2.96 2.98 2.99
These values suggest that the limit is indeed 3.

MA 114 ©UK Mathematics Department

6 CHAPTER 1. RECURSIVE SEQUENCES

3
Example 1.7. Let anC1 D . Find the fixed points of this recursion, and investigate the
an
limiting behavior of an when a0 is not equal to a fixed point.
To find the fixed points, we need to solve

3
aD :
a
p
2 D 3; hence, a D ˙ 3. These are the two fixed points. If
This equation
p is equivalent
p to ap p p
a0 D p 3, then a1 D 3, a2 D 3,and so on, and likewise, if a0 D 3,then a1 D 3,
a2 D 3, and so on.
Let’s start with a value that is not equal to one of the fixed points — say, a0 D 2. Using
the recursion, we find that

3 3
a1 D D
a0 2
3 3
a2 D D 3
D2
a1 2
3 3
a3 D D
a2 2
3 3
a4 D D 3
D2
a3 2

and so on — successive terms alternate between 2 and 3/2.

Try another initial value, say, a0 D 3. Then

3 3
a1 D D D1
a0 3
3 3
a2 D D D3
a1 1
3 3
a3 D D D1
a2 3
3 3
a4 D D D3
a3 1

and so on. Successive terms now alternate between 3 and 1. In this specific example
alternating between two values, one of which is the initial value, happens with any initial
value that is not one of the fixed points. Specifically, we have

3
a1 D
a0
3 3
a2 D D D a0
a1 3
a0

Thus, a3 D a1 , a4 D a2 D a0 , and so on.

MA 114 ©UK Mathematics Department

1.1. LIMITS OF RECURSIVE SEQUENCES 7

The last two examples illustrate that fixed points are only candidates for limits and
that, depending on the initial condition, the sequence fan g may or may not converge to a
given fixed point. If we know, however, that a sequence fan g does converge, then the limit
of the sequence must be one of the fixed points.
This leaves us with the question of how do we know when a recursive sequence is
going to converge. We refer to Theorem 11.12 in the text, the Monotonic Sequence Theorem.

Theorem 1.1 (Monotonic Sequence Theorem). Every bounded, monotonic sequence converges.

If we are given a sequence in a recursive formula, an D f .an 1 /, we will need to check

that it is bounded, check that it is monotonic (increasing or decreasing), and then find any
fixed points. We can check if the given function, f .x/, is increasing or decreasing by using
derivatives, but this does not help us with the monotonicity of the sequence directly.
There are two crucial conditions that must be met to insure the monotonicity of the
sequence. Consider the recursive sequence with anC1 D f .an / and a1 is some given value.
Solve the equation f .x/ D x and assume that we find two fixed points a and b so that
f .a/ D a and f .b/ D b.

1. No fixed point of f is located between a and b.

Then, for a < x < b, the graph of y D f .x/ lies either entirely above or entirely
below the graph of y D x, the diagonal.

2. The function maps the interval .a; b/ to itself.

By this we mean that for all x 2 .a; b/, a < f .x/ < b.

Based on these two conditions we can see that if the graph of f lies above the line
y D x, then a2 D f .a1 / > a1 and the sequence will be increasing and lim an D b. If the
n!1
graph lies below the line y D x, then a2 D f .a1 / < a1 and the sequence will be decreasing
and lim an D a.
n!1

5
Example 1.8. Consider the recursive sequence anC1 D with a1 D 4. We want to
6 an
show that fan g converges and find its limit.
5
First, we look at the function: f .x/ D . Note that we have that anC1 D f .an / for
6 x
all n D 1; 2; 3; : : :, so this function generates our sequence.

Step 1 Find the fixed points.

5
D x ) 6x x2 D 5 ) x2 6x C 5 D 0 ) x D 1 or x D 5:
6 x

Step 2 Note that for x > 1 (which are the only values in which we are interested) we have
that 1  f .x/ < 6 on .1; 5/. Thus, the function and hence the sequence are bounded.

Step 3 Note that for all 1 < x < 5 we have that 1 < f .x/ < 5, so the function maps the
interval .1; 5/ to itself.

MA 114 ©UK Mathematics Department

8 CHAPTER 1. RECURSIVE SEQUENCES

Step 4 Note that the initial point a1 lies between the two fixed points, so we only need to
know that the sequence is monotonic on the interval .1; 5/, between the fixed points.
5
This is easy since f 0 .x/ D > 0 for all x ¤ 6. Hence, f is increasing. Also,
.6 x/2
f 00 .x/ D 10=.6 x/3 and the graph is concave up. Thus, the graph must lie below
the line y D x and the sequence is decreasing. Thus, since we start at 4, the limit will
be 1.

n 1 2 3 4 5 6 7 8 9 10
an 4 2.50 1.429 1.094 1.019 1.004 1.001 1.000 1.000 1.000006

1.2 Examples of Recursive Processes

1. Newton’s Method: In Calculus I we saw that we could find the root of an equation
f .x/ D 0 by iterating the recursive formula

f .xn /
xnC1 D xn :
f 0 .xn /

There is no general formula for the nth term.

2. Compound interest/population growth: The growth of an investment paying i % per

annum compounded n times per year from the kth period to the .k C 1/st period is
given by  
i
AkC1 D Ak 1 C :
n
There is a general formula for the kth term.

3. Logistic population growth: Nt C1 D Nt Œ1 C R.1 Nt =K/, where K is the carrying

capacity of the environment and R is the growth parameter of the population.

4. Drug concentration: A drug is administered to a patient at the same time every day.
Suppose the concentration of the drug is Cn (measured in mg/mL) after the injection
on the nth day. Before the injection the next day, only 30% of the drug present on the
preceding day remains in the bloodstream. If the daily dose raises the concentration
by 0.2 mg/mL, the concentration on the next day is CnC1 D 0:3Cn C 0:2.
There is a general formula for the nth day.

1.3 Exercises
Check that the following sequences converge and find the limit.
1
1. anC1 D .an C 8/, a0 D 4.
2
3
2. anC1 D an2 2an C 2, a0 D .
2

MA 114 ©UK Mathematics Department

1.4. REFERENCES 9

p
3. anC1 D 24 2an , a0 D 11.

4. anC1 D 2an 2=3 , a0 D 1

1
5. anC1 D 2 , a0 D 5
2 C an
5an
6. anC1 D , a0 D 1
3 C an
 
1 9
7. anC1 D an C , a0 D 15
2 an

1.4 References
Neuhauser, Claudia, Calculus for Biology and Medicine, Third Edition, Pearson, 2010.
Stewart, James, Calculus: Early Transcendentals, Eighth Edition, Cengage Learning, 2015.
Krainer, Thomas, ”Recursive sequences in first-year calculus,” International Journal of Math-
ematics Education in Science and Technology, 47(2016), 299–314.

MA 114 ©UK Mathematics Department