Chapter 7   Recurrence Relations


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

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


[References]

1. Discrete Math - 7th Edition , Richard Johnsonbaugh, Pearson

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


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

                           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




Copyright @ 2018 SKKU Matrix Lab. All rights reserved.
Made by Manager: Prof. Sang-Gu Lee and Dr. Jae Hwa Lee
*This research was supported by Basic Science Research Program through the National Research Foundation of Korea (NRF) funded by the Ministry of Education (2017R1D1A1B03035865).