Formulation Of Recurrence Relation

FORMULATION OF RECURRENCE RELATION: Before we proceed with discussing various methods of solving recurrence relation, we shall formulate some recurrence relation.

Example : With reference to Example 5.3, let Hn denote the number of moves required to solve the puzzle with n discs. Let us define Hn recursively.

Solution: Clearly, H1 = 1.
Consider top (n–1) discs. We can move these discs to the middle peg using H_n–1 moves. The nth disc on the first peg can then moved to the third peg.
Finally, (n–1) discs from the middle peg can be moved to the third peg with first peg as auxiliary in Hn–1 moves. Thus, total number of moves needed to move n discs are: Hn = 2H_n–1 1. Hence the recurrence relation for the Tower of Hanoi is:
Hn = 1 if n = 1.
Hn = 2H_n–1 1 otherwise.

Example: Find recurrence relation and initial condition for the number of bit strings of length n that do not have two consecutive 0s.

Solution: Let an denote the number of bit strings of length n that do not contain two consecutive 0s. Number of bit strings of length one that follow the necessary rule are: string 0 and string 1. Thus, a₁ = 2. The number of bit strings of length 2 is: string 01, 10 and 11. Thus, a2 = 3. Now we shall consider the case n ≥ 3. The bit strings of length n that do not have two consecutive 0s are precisely those strings length n–1 with no consecutive 0s along with a 1 added 1 at the end of it (which is an–1 in number) and bit strings of length n–2 with no consecutive 0s with a 10 added at the end of it (which is a_n–2 in number). Thus, the recurrence relation is:
a_n = a_n–1 a_n–2 for n ≥ 3 with a₁ = 2 and a₂ = 3.