Chapter 7 Recurrence Relations
7.1 Introduction
7.2 Solving Recurrence Relations
7.3 Applications
In this section we will show that recurrence relation can be used to study and to solve counting problems.
7.1 Introduction
A recurrence relation defines a sequence by giving the th value in terms of its predecessors. The th value is given in terms of the immediately preceding value. In order for a recurrence relation to define a sequence, a “start up” value or values must be given. These start up values are initial conditions. A sequence is called a solution of a recurrence relation if its terms satisfy the recurrence relation.
Definition 1.1 


Example 1.2 

The Fibonacci sequence is the recurrence relation , . Initial conditions are , . 
Example 1.3 

A person invests at interest compounded annually. If represents the amount at the end of years, find a recurrence relation and initial conditions that define the sequence . 
Solution
After year the amount is
, where is initial amount.
After year the amount is
After years the amount is
, .
is initial condition.
.
Algorithm 1.4 
Computing Compound Interest 
This recursive algorithm computes the amount of money at the end of years assuming an initial amount of and an interest rate of compounded annually. Input: , the number of years Output: The amount of mony at the end of years 1. compound_interest (n) 2. if 3. return 4. return *compound_interest 5. 
Example 1.5 


Example 1.6 

denote the number of bit strings that do not contain the pattern . Develop a recurrence relation for , , and initial conditions that define the sequence . We will count the number of bit strings that do not contain the pattern . (a) that begin with (b) that begin with (c) that begin with 
Solution
By the Addition Principle
An bit string begins with and does not contain the pattern .
Then bit string following the initial does not contain the pattern .
Since any bit string not containing can follow the initial , there are strings of type .
An bit string begins with and does not contain the pattern ,
Then bit string following the initial cannot contain the pattern ; therefore, there are strings of type .
If an bit string begins with and does not contain the pattern .
Then the third bit must be .
The bit string following the initial cannot contain the pattern ; therefore, there are strings of type .
Thus
, .
By inspection, we find the initial conditions
, , .
Example 1.8 
Tower of Hanoi 

Cobweb simulation https://youtu.be/TjNjk6UjRs
Example 1.9 
The Cobweb in Economics 
An economics model in the supply and demand are given by linear equation.
The demand equation is
,
where is the price, is the quantity, and are positive parameters.
price increases the consumers demand less of the product.
The supply equation is
,
where is the price, is the quantity, is positive parameter.
price increases the manufacturer is willing to supply greater quantities.
An economics model
There is a time lag as the supply reacts to change.
Denote the discrete time intervals as .
The demand equation is
,
that is, at time , the quantity of the product will be sold at price .
The supply equation is
,
that is, one unit of time is required for the manufacturer to adjust the quantity , at time , to the price , at the prior time .
We solved equation for .
The demand equation for time is
recurrence relation
for price.
A cobweb with a stabilizing price
The price changes viewed graphically.
The initial price is
At time The manufacturer will be willing to supply the quantity .
We locate this quantity by moving horizontally to supply curve.
By moving vertically to the demand curve.
The market forces drive the price down to .
At price The manufacturer will be willing to supply the quantity at time .
By moving horizontally to the supply curve.
The market forces drive the price up to , as we can see by moving vertically to the demand curve.
By continuing this process, we obtain the “cobweb.”
For the supply and demand functions, the price approaches the intersection of the supply and demand curves.
This is not always the case.
The price fluctuates between and .
The price swings become more and more pronounced.
The behavior is determined by the slopes of the supply and demand lines.
To produce the fluctuating behavior of Figure ,
is the slope of the supply curve.
is the slope of the demand curve.
the price fluctuates between two values.
the price tends to the intersection of the supply and demand curves.
the increasing priceswing case.
Example 1.10 
Ackerman’s Function 
Ackerman’s function is the recurrence relations (1.11) , (1.12) , . The initial conditions (1.13) , Ackerman’s function is rapid rate of growth. 
The computation
by
by
by
by
Exercises 25, 26, 40, 41, 42, 43, 44, 46, 47, 48, 49, 50
7.2 Solving Recurrence Relations
Two methods of solving recurrence relation
(a) iteration
(b) linear homogeneous recurrence relation with constant coefficient
Example 2.1 

By iteration, solve the recurrence relation . The initial condition is . 
Solution
Replacing by in , we obtain
.
(2.2)
Replacing by in , we obtain
.
In general,
.
Setting in this last expression, we have
.
Taking , we obtain
for the sequence .
Example 2.2 

By iteration, solve the recurrence relation . The initial condition is . . 
Example 2.3 
Population Growth 
Assume that the deer population of Rustic County is at time . The increase from time to time is percent of the size at time . Write a recurrence relation and an initial condition that define the deer population at time and then solve the recurrence relation. 
Solution
is the deer population at time .
The initial condition is
.
The increase from time to time is .
The increase is of the size at time , we obtain recurrence relation
.
The recurrence relation may be solved by iteration;
.
exponential population growth
Example 2.4 


Solution
The recurrence relation is
.
The initial condition is
.
.
Example 2.5 

Solve the recurrence relation
for the price in the economics model of Example 1.9 by iteration. 
Solution
To simply the notation, we set .
(2.4)
If , the term .
If , (2.4) shows that oscillates between and .
If , (2.4) shows that the differences between successive prices increase.
Definition 2.6 


The recurrence relation in the definition is linear because the righthand side is a sum of
previous terms of the sequence each multiplied by a function of . The recurrence relation is homogeneous because no terms occur that are not multiples of the s.
A linear homogeneous recurrence relation of order with constant coefficient, with initial conditions
, , , ,
uniquely defines a sequence , , .
Example 2.7 


Example 2.8 

The nonlinear recurrence relations (2.8) is not a linear homogeneous recurrence relation with constant coefficients. 
Example 2.9 

The recurrence relations
is a linear nonhomogeneous recurrence relation with constant coefficients. The right side of the equation is not zero. 
Example 2.10 

The recurrence relations
is not a linear homogeneous recurrence relation with constant coefficients. Coefficient is not constant. is a linear homogeneous recurrence relation with nonconstant coefficients. 
General method of solving linear homogeneous recurrence relation with constant coefficients.
By the recurrence relation
(2.9)
and initial conditions
(2.10) , .
The characteristic equation of is .
, .
Let , then
Sequence is geometric sequence of common ratio with initial term .
Let , then
Sequence is geometric sequence of common ratio with initial term .
Theorem 2.11 


Example 2.12 
More Population Growth 
Assume that the deer population of Rustic Country is at time and at time and that the increase from time to time is twice the increase from time to time . Write a recurrence relation and an initial condition that define the deer population at time and then solve the recurrence relation. 
Solution
is the deer population at time .
The initial conditions
, .
The increase from time to time is .
The increase from time to time is .
The recurrence relation
.
To solve this recurrence relation.
The quadratic equation is
, .
The sequence is
To satisfy the initial conditions, we must have
, .
Thus is
.
Example 2.13 

Find an formula for the Fibonacci sequence. The Fibonacci sequence is defined by the linear homogeneous second order recurrence relation , . and initial conditions , . 
Solution
By using the quadratic formula to solve
.
The solution is
To satisfy the initial conditions, we must have
Solving these equations for and is
, .
An formula for the Fibonacci sequence is
.
Theorem 2.14 


Example 2.15 

Solve the recurrence relation (2.18) subject to the initial conditions . 
Solution By using the quadratic formula to solve
.
At this point, we have two solutions and of (2.18), given by
,
The general solutions of is
.
To satisfy the initial conditions, we must have
, .
The solution of is
.
Exercises 36, 37, 38 39, 41, 44, 47, 53