그림입니다.
원본 그림의 이름: CLP000022e82d2b.bmp
원본 그림의 크기: 가로 511pixel, 세로 184pixel

그림입니다.
원본 그림의 이름: CLP000022e80001.bmp
원본 그림의 크기: 가로 144pixel, 세로 156pixel


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

 

그림입니다.
원본 그림의 이름: CLP000022e80002.bmp
원본 그림의 크기: 가로 806pixel, 세로 107pixel



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.

. 그림입니다.
원본 그림의 이름: CLP000113980012.bmp
원본 그림의 크기: 가로 23pixel, 세로 22pixel



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

 

그림입니다.
원본 그림의 이름: CLP000022e80004.bmp
원본 그림의 크기: 가로 803pixel, 세로 210pixel



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


,    ,    그림입니다.
원본 그림의 이름: CLP000113980012.bmp
원본 그림의 크기: 가로 23pixel, 세로 22pixel



Example  1.8

  Tower of Hanoi

그림입니다.
원본 그림의 이름: CLP000022e80005.bmp
원본 그림의 크기: 가로 808pixel, 세로 177pixel

그림입니다.
원본 그림의 이름: CLP000022e80006.bmp
원본 그림의 크기: 가로 721pixel, 세로 273pixel

그림입니다.
원본 그림의 이름: CLP000022e80008.bmp
원본 그림의 크기: 가로 843pixel, 세로 416pixel

그림입니다.
원본 그림의 이름: CLP000022e80007.bmp
원본 그림의 크기: 가로 723pixel, 세로 287pixel

그림입니다.
원본 그림의 이름: CLP000022e80009.bmp
원본 그림의 크기: 가로 822pixel, 세로 389pixel그림입니다.
원본 그림의 이름: CLP000113980012.bmp
원본 그림의 크기: 가로 23pixel, 세로 22pixel


                           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. 그림입니다.
원본 그림의 이름: CLP000113980012.bmp
원본 그림의 크기: 가로 23pixel, 세로 22pixel


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 . 그림입니다.
원본 그림의 이름: CLP000113980012.bmp
원본 그림의 크기: 가로 23pixel, 세로 22pixel



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;

그림입니다.
원본 그림의 이름: CLP000113980012.bmp
원본 그림의 크기: 가로 23pixel, 세로 22pixel

                                                 exponential population growth


Example  2.4

 

 그림입니다.
원본 그림의 이름: CLP000022e8000a.bmp
원본 그림의 크기: 가로 801pixel, 세로 239pixel

Solution

The recurrence relation is

.

The initial condition is

.

  

  

  

  

       

  

  

  그림입니다.
원본 그림의 이름: CLP000113980012.bmp
원본 그림의 크기: 가로 23pixel, 세로 22pixel



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.  그림입니다.
원본 그림의 이름: CLP000113980012.bmp
원본 그림의 크기: 가로 23pixel, 세로 22pixel


 Definition  2.6

 

 그림입니다.
원본 그림의 이름: CLP000022e8000b.bmp
원본 그림의 크기: 가로 804pixel, 세로 128pixel

 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 , , 그림입니다.
원본 그림의 이름: CLP000113980012.bmp
원본 그림의 크기: 가로 23pixel, 세로 22pixel



Example  2.7

 

그림입니다.
원본 그림의 이름: CLP000022e8000c.bmp
원본 그림의 크기: 가로 805pixel, 세로 279pixel



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 .

        

        

        

          그림입니다.
원본 그림의 이름: CLP000113980012.bmp
원본 그림의 크기: 가로 23pixel, 세로 22pixel


 Theorem  2.11

 

그림입니다.
원본 그림의 이름: CLP000022e8000d.bmp
원본 그림의 크기: 가로 797pixel, 세로 507pixel


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

그림입니다.
원본 그림의 이름: CLP000113980012.bmp
원본 그림의 크기: 가로 23pixel, 세로 22pixel


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

그림입니다.
원본 그림의 이름: CLP000113980012.bmp
원본 그림의 크기: 가로 23pixel, 세로 22pixel


 Theorem  2.14

 

그림입니다.
원본 그림의 이름: CLP000022e8000e.bmp
원본 그림의 크기: 가로 795pixel, 세로 358pixel


그림입니다.
원본 그림의 이름: CLP000022e8000f.bmp
원본 그림의 크기: 가로 612pixel, 세로 219pixel

그림입니다.
원본 그림의 이름: CLP000022e80011.bmp
원본 그림의 크기: 가로 601pixel, 세로 210pixel

그림입니다.
원본 그림의 이름: CLP000022e80012.bmp
원본 그림의 크기: 가로 613pixel, 세로 199pixel

그림입니다.
원본 그림의 이름: CLP000022e80013.bmp
원본 그림의 크기: 가로 626pixel, 세로 239pixel 그림입니다.
원본 그림의 이름: CLP000113980012.bmp
원본 그림의 크기: 가로 23pixel, 세로 22pixel


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

그림입니다.
원본 그림의 이름: CLP000113980012.bmp
원본 그림의 크기: 가로 23pixel, 세로 22pixel

그림입니다.
원본 그림의 이름: CLP000022e80014.bmp
원본 그림의 크기: 가로 625pixel, 세로 545pixel

그림입니다.
원본 그림의 이름: CLP00013d4853e4.bmp
원본 그림의 크기: 가로 525pixel, 세로 284pixel 


             Exercises  36, 37, 38 39, 41, 44, 47, 53