Skip to content

Recurrence Relation and its Solution

September 1, 2012

  • Introduction:

The meaning of the term recursion is simply defining something in terms of itself. In order to define any sequence that is recursive we have to specify at least one of the initial terms of that sequence and a rule to determine the subsequent terms of that sequence. We are very familiar with many a few of such examples such as to define the factorial of a number we need to multiply the number with the factorial of the preceding number, where factorial of 0 is 1, i.e.

N! = N * (N-1)! Where 0! =1

Now the above more formally can be represented in the notations that we use very often in the context of recurrence relation as below

Fn = n * Fn-1 where F0 = 1 and n≥1

  • Example: Find the total number of bit strings of length 5 that do not have 2 consecutive 0s.
  • Solution: Let an be the number that denotes the number of such strings of length n that do not have consecutive 0s. Now to find a recurrence relation for {an } it can be noted that by sum rule the number of bit strings of length n that do not have 2 consecutive 0s is equal to number of such bit strings ending with a 0 plus the number of such bit strings ending with a 1. We assume that n≥1, i.e. there are at least 3 bits in the string.

The bit strings of length n that do not have 2 consecutive 0s and end with a 1 are precisely the bit strings of length n-1 with no 2 consecutive 0s and a 1 added at the end. Consequently there are an-1 such bit strings.

The bit strings of length n that do not have 2 consecutive 0s and end with a 0 must have their (n-1)th bit as a 1. So these are precisely the bit strings of length n-2 with no 2 consecutive 0s and 10 added at the end. Consequently there are an-2 such bit strings.

Hence the total number of bit strings of length n that do not have 2 consecutive 0s is given by

\ an = an-1  +  an-2  for all n≥3 where a1 = 2 (either 0 or 1) and a2 = 3 (either 01 or 10 or 11 ).

So to find the number of bit strings of length 5 having no 2 consecutive 0s

 = a5

 =a4 + a3

= (a2 + a3) + (a1 + a2)

= 3 + (a1 + a2) + 2 + 3

= 3 + 2 + 3 + 2 + 3

=13

v Definition:

A recurrence relation for the sequence {an} is an equation that expresses an in terms of one or more of the previous terms of the sequence, namely a0, a1, . . . , an-1 for all integers n with n≥n0 where n0 is a non negative integer. A sequence is said to be the solution of a recurrence relation if its terms satisfy the recurrence relation.

v Famous Problems:

In this section we will present a couple of famous problems that are often used in the context of recurrence relation. First we will introduce the Fibonacci numbers and then the Tower of Hanoi problem.

  • Rabbits and the Fibonacci Numbers:  Let us consider the problem that was originally posed by Leonardo Pisano, as known as Fibonacci. A young pair of rabbits one of each sex is placed in an island. A pair of rabbits does not breed until they are 2 months old. After they are 2 months old each pair of rabbits produces another pair each month. After n months the number of rabbit pairs that are in the island is called the nth Fibonacci number. From the figure given below we can understand the scenario. The last column of the figure refers to the Fibonacci numbers which is none initially, 1 after a month is elapsed, 1 again after 2 months are gone, and then 3,5,8 after 3,4 and 5 months respectively and so on.

  • The Tower of Hanoi:  A popular puzzle of late 19th century invented by French Mathematician Lucas called the Tower of Hanoi consists of 3 pegs mounted on a board together with disks of different sizes. Initially these disks are placed on the first peg in order of their size with the largest being placed at the bottom as shown in figure below. The rules of puzzle allow the disks to be moved one at a time from one peg to another keeping in mind a larger disk can’t ever be placed over a smaller disk. The goal of the puzzle is to have all the disks in the second peg in order of size with the largest at the bottom.
  • In the figure below we can see 3 pegs named as A, B and C. Initially all the disks are placed in peg A. The goal thus is to move the disks from Peg A to Peg B using Peg C as a temporary peg. We can divide the task into three of its subtasks as i)                    Move the top n-1 disks from Peg A to Peg C using Peg B as intermediate.ii)                  Move the only remaining disk from peg A to Peg B.iii)                Move the n-1 disks to peg B that are currently placed in peg C using peg A as intermediate. 

     

    And hence we find that all the disks have been moved from peg A to peg B and that too in order.

    v Formulation of Recurrence Relation for the above problems:

                      In this section we shall see how the above problems can be represented in terms of recurrence relations. One may ask why we are trying to do so. The answer is quite simple. If we are asked that “what is the value of the 50th Fibonacci number” or “how many moves do we need to solve the Tower of Hanoi problem for say 20 disks” then we can’t simply choose the iterative method in order to find the solution. The motive of building a recurrence relation is that if we have the recurrence relation then its solution will help us to find that value. In that case we would have an equation with a dependent variable and an independent one. If we put the value of the independent variable (number of disks in case of the Tower of Hanoi example and the value of n in case of Fibonacci numbers) in the equation which satisfies the given recurrence relation then the value of the dependent variable (number of moves in case of the Tower of Hanoi example and the value of the generated nth Fibonacci number in case of the Fibonacci sequence) comes out. So now we find the recurrence relations for both of the problems as given below.

    • Rabbits and the Fibonacci Numbers:  Let Fn be the value of the nth Fibonacci number i.e. the number of rabbit pairs in the island after n months. It can be noted that at the end of the first month there is only a young pair in the island and since the pair is still young it doesn’t breed during the second month as well. So values of both F1 and F2 are 1. Now to find the number of pairs in the island after n months add the number of pairs in the previous month (i.e. Fn-1) and the number of newborn pairs(i.e. Fn-2 , because every newborn comes from at least 2 months old pair). And hence the recurrence relation can be given as

    Fn = Fn-1  +  Fn-2  for all n≥3 where F1 = 1 and F2 = 1.

    • The Tower of Hanoi:  Let Hn be the number of moves needed to solve the Tower of Hanoi problem with n disks. Now as we have stated early in order to do the complete task we decompose the whole thing into 3 subtasks.

    i)                    To move the top n-1 disks from Peg A to Peg C using Peg B as intermediate we would need Hn-1 number of moves.

    ii)                  Then 1 more move is needed to move the only remaining disk from peg A to peg B.

    iii)                Then to move n-1 disks from peg C to peg B we would need Hn-1 more moves.

    Adding up the above 3 we get the total number of moves which is given as below

    Hn = Hn-1 + 1 + Hn-1

    = 2Hn-1 + 1; where n≥1 and H1=1 since we need only a single move for moving a single disk from peg A to peg B and no peg C is required.

     

    v Methods of Solution of Recurrence Relations:

    We have already stated the essence of finding the solution of a given recurrence relation. In this section we shall discuss about how this can be done. Mainly we shall discuss 2 techniques for doing so: iterative method and characteristic equation method.

    • Iterative Method: Here we consider the recurrence relation that we have obtained for the Tower of Hanoi problem. In this section we will see how to solve this kind of an equation in an iterative manner.

    We had the recurrence relation as

    Hn = 2Hn-1 + 1

    = 2(2Hn-2 + 1) + 1 = 22 Hn-2 + 2 + 1

    = 22(2Hn-3 + 1) + 2 + 1 = 23 Hn-3 +22 + 2 + 1

    .

    .

    .

    = 2n-1H1 + 2n-2 + 2n-3 + . . . + 2 + 1

    = 2n-1+ 2n-2 + 2n-3 + . . . + 2 + 1 [putting H1 =1]

    = 2n – 1

    Hence the iterative method has given the solution of the above recurrence relation Hn = 2Hn-1 + 1 with the initial condition H1 = 1.

    However this method of solution may not be convenient for a large variety of recurrence relations. For this reason we are introducing the next method of solution, i.e. solution using characteristic equations.

    • Characteristic Equation Method: By this method we can solve a wide variety of linear equations both homogenous and non homogeneous. First we discuss the methods of solving the homogeneous equations and then we shall discuss about the non homogenous ones.
    • Linear Homogeneous Equations of Degree k: A linear homogeneous recurrence relation of degree k with constant coefficients is the one of the form

    an = c1an-1 +  c2an-2 + . . . + ckan-k ; where c1,c2, . . ., ck are real constants and ck≠ 0.

    The above is called linear because every term in the right hand side is a sum of previous terms of sequence each multiplied by a function of n. The above is said to be homogeneous as no terms occur that are not the multiples of ajs. Finally the degree or the order of the equation is k as a number in the sequence is expressed in terms of previous k number of terms of the same sequence. There are 3 basic rules of finding a solution to such equations and these are as stated below:

    Rule 1: If λ is a root of the characteristic equation of a linear homogeneous equation then xn = λn is a solution to the given homogeneous equation.

    Rule 2: If λ1 and λ2 are the 2 distinct roots of the characteristic equation of the linear homogenous equation then xn = A(λ1)n+ B(λ2)n is a solution of the homogenous equation where A and B are 2 constants.

    Rule 3: If λ is a multiple root of the characteristic equation of the given homogeneous equation with multiplicity r then x = λn, nλn, n2λn, . . . , nr-1λn are all solutions to the given homogeneous equation.

    Now let us see some of the examples given below.

    Example: Find a solution to the recurrence relation for the Fibonacci sequence an = an-1 +  an-2  for all n≥2 where a0 = 0 and a1 = 1.

    Solution: Let us assume that λ is a root of the characteristic equation for the given recurrence relation. So applying the 1st rule we get an = λn. So the characteristic equation would look like

                                  λn = λn-1 + λn-2

    or,  λ2 = λ + 1 [dividing both sides by λn-2]

    or,  λ2 – λ – 1 = 0

    or, λ = (1 ± √5) /2

    i.e. λ1 = (1 + √5) /2 and λ2 = (1 – √5) /2 ; since these are 2 distinct roots of the  characteristic equation then the solution of the given homogeneous equation will be

    an = A((1 + √5) /2)n + B((1 – √5) /2)n ; A,B are constants.

    . . . . . . . . . . (i)

    Now putting the values for initial conditions we have 2 more equations as

    a0 = A((1 + √5) /2)0 + B((1 – √5) /2)0

                                         or, A+B = 0 . . . . . . . . . . . . . . . . . . . . . . . (ii)

    and                       a1 = A((1 + √5) /2)1 + B((1 – √5) /2)1

                                         or, A(1 + √5) /2 + B(1 – √5) /2 = 1 . . . . . (iii)

    From (ii) and (iii) we find the values for constants A and B as A=1 / √5 and B = -1 / √5

    Finally putting these values in the equation (i) we have the solution to the given homogeneous recurrence relation as

    an = (1 / √5 )((1 + √5) /2)+  (-1 / √5)((1 – √5) /2)n                 

    Example: Find the solution to the linear homogeneous recurrence relation an+2 – 8an+1 + 16an = 0 for all n≥0 where a0 = 0 and a1 = 8.

    .

    Solution: Let us assume that λ is a root of the characteristic equation for the given recurrence relation. So applying the 1st rule we get an = λn. So the characteristic equation would look like

                                  λn+2 – 8λn+1 + 16λn = 0

    or,  λ2 – 8λ + 16 = 0 [dividing both sides by λn]

    or,  (λ – 4)2 = 0

    Since λ is a multiple root of the characteristic equation with multiplicity 2 so the solution of the given homogeneous recurrence relation is

    an = A.4n + B.n.4; where A and B are constants.

    . . . . . . . . . . (i)

    Now putting the values for initial conditions we have 2 more equations as

    a0 = A.40 + B.0.40

    or, A= 0                          . . . . . . . . . . (ii)

    a1 = A.41 + B.0.41

    or, 4A + 4B = 8

    or, 4B = 8

    or, B = 2                                . . . . . . . . . . .(iii)

    Finally putting the values obtained from (ii) and (iii) in the equation (i) we have the solution to the given homogeneous recurrence relation as

    an = 2n.4n

    • Linear Non Homogeneous Equations: A linear recurrence relation is said to be non homogeneous if unlike the previous case there exists at least a term that is not multiple of any aj for all values of j. A linear non homogeneous recurrence relation with constant coefficients is said to take the form as given below

    an = c1an-1 +  c2an-2 + . . . + ckan-k + f(n); where c1,c2, . . ., ck are real constants and f(n) is a function non identically zero depending only on n. Here the recurrence relation

    an = c1an-1 +  c2an-2 + . . . + ckan-k  

    is said to be the underlying homogeneous recurrence relation which plays a vital role in order to find the solution of the non homogeneous recurrence relation. Again there are 3 general rules to find the solution of a given non homogeneous recurrence relation as stated below.

    Rule 1: The general solution to a given non homogeneous recurrence relation is obtained by adding the general solution of the corresponding homogeneous recurrence relation to any particular solution of the non homogeneous recurrence relation.

    Rule 2: A particular solution to a given non homogeneous recurrence relation can be found by appropriately selecting the constants to the general solution to the homogeneous recurrence relation satisfied by the forcing sequence.

    Rule 3: If rule 2 fails then take the trial solution which didn’t work, then multiply it by n and try again. Repeat this procedure as often as required.

    One can use the table given below as a look up table in order to choose the appropriate trial solution for a given forcing sequence.

    Forcing Sequence (fn)

    Trial Sequence (Pn)

    a

    A

    an+b

    An+B

    arnr + ar-1nr-1 + . . . + a0

    Arnr + Ar-1nr-1 + . . . + A0

    n

    n

    λn(arnr + ar-1nr-1 + . . . + a0)

    λn(Arnr + Ar-1nr-1 + . . . + A0)

    The table below shows some examples of how these trial solutions are selected depending upon the given forcing sequence.

    Forcing Sequence (fn)

    Trial Sequence (Pn)

    1

    A

    n

    An+B

    2n

    A.2n

    3n2+5

    An2+Bn+C

    2n+4(-5)n

    A.2n+B(-5)n

    1+n.2n

    A+(Bn+C).2n

    2.7n+3n+4

    A.7n+Bn+C

    6n2.3n

    (An2+Bn+C).3n

    Now let us see the example given below.

    Example: Find the solution for the linear non homogeneous recurrence relation xn – 2xn-1 = 6n for all values of n≥2, the initial condition being x1=2.

    Solution: First of all we got to solve the underlying homogeneous equation which is xn – 2xn-1 = 0. Let λ be the root of the characteristic equation of the underlying homogeneous equation. So the characteristic equation would be

                                        λn – 2λn-1 =0

    or,       λ -2 = 0

    or,       λ = 2

    Hence the solution to the homogenous equation will be xn = A.2n . . . (i)

    The given forcing sequence is f(n) = 6n

    Thus the chosen trial solution is Pn = Bn+C . . . . (ii)

    Now since Bn+C is a particular solution to the non homogeneous recurrence relation then it should satisfy the equation if we replace the xn by Bn+C. Hence by doing that we get

    ( Bn + C ) – 2 ( B ( n-1 ) + C ) = 6n

    Or,       -Bn – C + 2B = 6n

    Hence by equating the terms of both sides we get

    -Bn = 6n

    Or,       B = -6

    And                 2B – C = 0

    Or,       C = -12

    Therefore the actual solution to the given non homogeneous recurrence relation is found by adding up (i) and (ii) as stated in rule 1 and it will be

    xn = A.2n – 6n – 12

    Putting the value of the initial condition we get

    x1 = A.21 – 6.(1) – 12 = 2

    or,       A = 10

    And hence the final solution to the given non homogeneous recurrence relation will be

    xn = 10.(2)n – 6n – 12

    NOTE

    It can be noted that for some trial sequences after putting it on the given equation it might happen that all the terms from both sides of the equation are cancelled out. In that case we can’t work with the chosen trial solution. We then have to choose a next trial solution and see whether that works or not. That trial solution is chosen by multiplying the previous one with n. Say the first trial solution was Pn = (An+B), then the next one has to be Pn = (An2+Bn). And we repeat this as often as required as stated above in rule 2.

    • Method of Generating Function: If a0, a1, . . . , an is a finite sequence of numbers then the generating function for the sequence is defined by

    G(z) = iz ;where z is an abstract symbol.

    So in order to solve a given recurrence relation by the method of generating functions we first have to find out the generating function that satisfies the recurrence relation and then using that we would need to solve the recurrence relation.

    Let us take the example below, it will illustrate the whole thing.

    Example: Find out the solution for yn + 2yn-1 – 15 yn-2 = 0, where n≥2 and y0 = 0, y1 = 1 by the method of generating functions.

    Solution: Multiplying the given equation by zn and taking the sum over n we get

    nzn = -2n-1zn + 15n-2zn

    Or,       G(z) – y0 – y1z = -2z            (G(z) – y0) + 15z2 G(z)

    Or,       G(z)  – z = -2zG(z)  + 15z2 G(z)

    Or,       G(z) + 2zG(z) + 15z2G(z) = z

    Or,       G(z) = z / (1 + 2z – 15z2)

    Or,       G(z) =

    This is the required generating function for the given recurrence relation. Now we can rewrite the above as shown below

    G(z) =  +     . . . (i)

    Or,       z = A(1-3z) + B(1+5z)

    Or,       z = A+B + z(5B-3A)

    Equating both sides we get

    A + B = 0 . . . (ii)

    -3A + 5B = 1 . . . (iii)

    From (ii) and (iii) we have the values for A and B as A= and B =  that are in turn put into (i) resulting in

    G(z) =  (1+5z)-1  +  (1-3z)-1            . . . (iv)

    Now we know that

    (1+5z)-1 = 1 – 5z + (5z)2 – (5z)3 + . . . + ∞

    (1-3z)-1 = 1 + 3z + (3z)2 + (3z)3 + . . . + ∞

    And it can also be noted that nth terms of the sequences will be (-5)n and 3n respectively. So replacing the terms (1+5z)-1 and (1-3z)-1 in the equation (iv) by these values we get

    yn =  (-5)+  3n

    and it is the solution of the given recurrence relation.

    v Contributions to Computer Programming:

    • There are many such algorithms that are very difficult to implement without recursion, for example, the Tower of Hanoi problem. The amount of stack it would need is quite difficult for us to maintain by the programmer himself and that amount will grow exponentially as the value of the input grows.
    • Some approaches are such that are very convenient and self explanatory. It increases the readability of the program and also the understandability to the code. One of such approaches is Divide and Conquer, where in order to solve a problem we try to find out the solution to the smaller sub-problems of the actual problem and then by merging these solutions to the sub-problems we get the solution to the actual problem which is much larger. It can be easily noted that this particular approach is completely standing on the basis of recurrence relations.

    v When to Avoid Recursion:               It is not that all the recursive problems should be implemented recursively for the sake of simplicity and understandability. We have given an example below that will help us to understand why it is so.

    Let us consider the scenario of calculating the value of the 6th Fibonacci number. Then the recursion tree will look like something as shown below:

    So one can see that when we are trying to calculate the 6th Fibonacci number have to calculate the values for 3rd, 4th and 5th Fibonacci numbers thrice and twice and once respectively. And as the value of n grows the recursion tree will also grow such as it would need a huge number of redundant calculations. Hence it will be better either to use the iterative method or make use of Dynamic Programming approach where once a Fibonacci number is calculated it is put as an entry of the dynamic look up table, and whenever we need the value again we refer to the table instead of recalculating its value, and in the process reducing a good amount of complexity.

    v Applications:          

    • Some of the best-known recurrence relations have their origins in the attempt to model population dynamics. For example, the Fibonacci numbers were once used as a model for the growth of a rabbit population.
    • In digital signal processing, recurrence relations can model feedback in a system, where outputs at one time become inputs for future time.
    • Recurrence relations, especially linear recurrence relations, are used extensively in both theoretical and empirical economics. In particular, in macroeconomics one might develop a model of various broad sectors of the economy (the financial sector, the goods sector etc.) in which some agents’ actions depend on lagged variables. The model would then be solved for current values of key variables.

    v References and Bibliography:            

     

    • Web References

    http://en.wikipedia.org/wiki/Recurrence_relation

    http://library.thinkquest.org/27890/theSeries2.html

    http://hcmop.wordpress.com/2012/04/20/using-characteristic-equation-to-solve-general-linear-recurrence-relations/

     

    • Books

    Discrete Mathematics and its Applications

    6th Edition

    By Kenneth H. Rosen

    McGraw-Hill International Edition

     

    • Image Courtesies

    http://blog.marquiswang.com/wpcontent/uploads/2010/02/Untitled.png

    http://www.cs.berkeley.edu/~bh/v1ch8/hanoi4.gif

    http://www.cs.ucsb.edu/~pconrad/cs40/images/ch07_jpeg/07_1_01.jpg

Advertisements

From → Academics

Leave a Comment

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: