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/Tj-Njk6UjRs

 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 price-swing 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 right-hand 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