Characteristic equations, Fibonacci Numbers, Generating functions, Recurrence relations, Tower of Hanoi

# Recurrence Relation and its Solution

*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

F_{n} = n * F_{n-1 }where F_{0} = 1 and n≥1

**Example:***Find the total number of bit strings of length 5 that do not have 2 consecutive 0s.***Solution:***Let a*_{n }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 {a_{n }} 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 a _{n-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 a_{n-2} such bit strings. *

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

*\** a _{n }*=

*a*

_{n-1 }+_{ }a_{n-2 }*for all*n≥3

*where*

*a*= 2 (either 0 or 1)

_{1 }*and*

*a*= 3 (either 01 or 10 or 11 ).

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

* **= a _{5}*

_{ }*=a _{4 }+ a_{3 }*

*= (a _{2} + a_{3}) + (a_{1 }+ a_{2})*

*= 3 + (a _{1 }+ a_{2}) + 2 + 3*

*= 3 + 2 + 3 + 2 + 3*

*=13*

v *Definition: *

*A recurrence relation for the sequence {a _{n}} is an equation that expresses a_{n }in terms of one or more of the previous terms of the sequence, namely a_{0}, a_{1}, . . . , a_{n-1} for all integers n with n≥n_{0} where n_{0 }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 n*^{th}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 19*^{th}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:*^{th}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 n^{th}_{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 F*_{n }be the value of the n^{th}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 F_{1}and F_{2}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. F_{n-1}) and the number of newborn pairs(i.e. F_{n-2 }, because every newborn comes from at least 2 months old pair). And hence the recurrence relation can be given as

*F*=_{n }*F*_{n-1 }+_{ }F_{n-2 }*for all*n≥3*where**F*= 1_{1 }*and**F*= 1._{2 }**The Tower of Hanoi:***Let H*_{n }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 H*_{n-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 H*_{n-1}more moves.*Adding up the above 3 we get the total number of moves which is given as below**H*_{n}= H_{n-1}+ 1 + H_{n-1}*= 2H*_{n-1}+ 1; where n≥1 and H_{1}=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

H

_{n }= 2H_{n-1 }+ 1= 2(2H

_{n-2 }+ 1) + 1 = 2^{2 }H_{n-2}+ 2 + 1= 2

^{2}(2H_{n-3 }+ 1) + 2 + 1 = 2^{3 }H_{n-3}+2^{2 }+ 2 + 1.

.

.

= 2

^{n-1}H_{1 }+ 2^{n-2 }+ 2^{n-3 }+ . . . + 2 + 1= 2

^{n-1}+ 2^{n-2 }+ 2^{n-3 }+ . . . + 2 + 1 [putting H_{1 }=1]= 2

^{n}– 1Hence the iterative method has given the solution of the above recurrence relation H

_{n }= 2H_{n-1 }+ 1 with the initial condition H_{1 }= 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

a

_{n}= c_{1}a_{n-1 }+_{ }c_{2}a_{n-2 }+ . . . + c_{k}a_{n-k }; where c_{1},c_{2}, . . ., c_{k }are real constants and c_{k}≠ 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 a_{j}s. 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 x_{n}= λ^{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 x_{n}= 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}, n^{2}λ^{n}, . . . , n^{r-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*a*=_{n }*a*_{n-1 }+_{ }a_{n-2 }*for all*n≥2*where**a*= 0_{0 }*and**a*= 1._{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 a_{n}= λ^{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 = 0or, λ = (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 bea

_{n }= 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

a

_{0}= A((1 + √5) /2)^{0 }+ B((1 – √5) /2)^{0}^{ }or, A+B = 0 . . . . . . . . . . . . . . . . . . . . . . . (ii)and a

_{1}= 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

a

_{n }= (1 / √5 )((1 + √5) /2)^{n }+ (-1 / √5)((1 – √5) /2)^{n }**Example:**Find the solution to the linear homogeneous recurrence relation a_{n+2 }– 8a_{n+1 }+ 16a_{n }= 0*for all*n≥0*where**a*= 0_{0 }*and**a*= 8._{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 a_{n}= λ^{n}. So the characteristic equation would look like^{n+2}– 8λ^{n+1}+ 16λ^{n }= 0or, λ

^{2}– 8λ + 16 = 0 [dividing both sides by λ^{n}]or, (λ – 4)

^{2}= 0Since λ is a multiple root of the characteristic equation with multiplicity 2 so the solution of the given homogeneous recurrence relation is

a

_{n }= A.4^{n }+ B.n.4^{n }; where A and B are constants.. . . . . . . . . . (i)

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

a

_{0 }= A.4^{0 }+ B.0.4^{0}or, A= 0 . . . . . . . . . . (ii)

a

_{1 }= A.4^{1 }+ B.0.4^{1}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

a

_{n }= 2n.4^{n}**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 a_{j }for all values of j. A linear non homogeneous recurrence relation with constant coefficients is said to take the form as given below

a

_{n}= c_{1}a_{n-1 }+_{ }c_{2}a_{n-2 }+ . . . + c_{k}a_{n-k }+ f(n); where c_{1},c_{2}, . . ., c_{k }are real constants and f(n) is a function non identically zero depending only on n. Here the recurrence relationa

_{n}= c_{1}a_{n-1 }+_{ }c_{2}a_{n-2 }+ . . . + c_{k}a_{n-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 (f*_{n})*Trial Sequence (P*_{n})a

A

an+b

An+B

a

_{r}n^{r }+ a_{r-1}n^{r-1 }+ . . . + a_{0}A

_{r}n^{r }+ A_{r-1}n^{r-1 }+ . . . + A_{0}aλ

^{n}Aλ

^{n}λ

^{n}(a_{r}n^{r }+ a_{r-1}n^{r-1 }+ . . . + a_{0})λ

^{n}(A_{r}n^{r }+ A_{r-1}n^{r-1 }+ . . . + A_{0})The table below shows some examples of how these trial solutions are selected depending upon the given forcing sequence.

*Forcing Sequence (f*_{n})*Trial Sequence (P*_{n})1

A

n

An+B

2

^{n}A.2

^{n}3n

^{2}+5An

^{2}+Bn+C2

^{n}+4(-5)^{n}A.2

^{n}+B(-5)^{n}1+n.2

^{n}A+(Bn+C).2

^{n}2.7

^{n}+3n+4A.7

^{n}+Bn+C6n

^{2}.3^{n}(An

^{2}+Bn+C).3^{n}Now let us see the example given below.

**Example:**Find the solution for the linear non homogeneous recurrence relation x_{n}– 2x_{n-1 }= 6n for all values of n≥2, the initial condition being x_{1}=2.**Solution:**First of all we got to solve the underlying homogeneous equation which is x_{n}– 2x_{n-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 }=0or, λ -2 = 0

or, λ = 2

Hence the solution to the homogenous equation will be x

_{n}= A.2^{n}. . . (i)The given forcing sequence is f(n) = 6n

Thus the chosen trial solution is P

_{n}= 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 x

_{n }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

x

_{n}= A.2^{n}– 6n – 12Putting the value of the initial condition we get

x

_{1}= A.2^{1}– 6.(1) – 12 = 2or, A = 10

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

x

_{n}= 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 P

_{n }= (An+B), then the next one has to be P_{n }= (An^{2}+Bn). And we repeat this as often as required as stated above in rule 2.**Method of Generating Function:**If a_{0}, a_{1}, . . . , a_{n }is a finite sequence of numbers then the generating function for the sequence is defined by

G(z) =

_{i}z^{i };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 y_{n }+ 2y_{n-1 }– 15 y_{n-2}= 0, where n≥2 and y_{0 }= 0, y_{1}= 1 by the method of generating functions.**Solution:**Multiplying the given equation by z^{n }and taking the sum over n we get_{n}z^{n}= -2_{n-1}z^{n}+ 15_{n-2}z^{n}Or, G(z) – y

_{0 }– y_{1}z = -2z (G(z) – y_{0}) + 15z^{2 }G(z)Or, G(z)

_{ }– z = -2zG(z) + 15z^{2 }G(z)Or, G(z) + 2zG(z) + 15z

^{2}G(z) = zOr, G(z) = z / (1 + 2z – 15z

^{2})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 n

^{th }terms of the sequences will be (-5)^{n}and 3^{n}respectively. So replacing the terms (1+5z)^{-1 }and (1-3z)^{-1}in the equation (iv) by these values we gety

_{n}= (-5)^{n }+ 3^{n}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

t 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.*When to Avoid Recursion: I*Let us consider the scenario of calculating the value of the 6

^{th}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 6

^{th}Fibonacci number have to calculate the values for 3^{rd}, 4^{th}and 5^{th}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***Books**

*Discrete Mathematics and its Applications**6*^{th}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*

From → Academics