B tech. Discrete mathematics (I. T & Comp. Science Engg.) Syllabus

FORMULATION OF RECURRENCE RELATION:

Before we proceed with discussing various methods of solving recurrence relation, we shall formulate some recurrence relation. The first example of formulation that we discuss is the problem of Tower of Hanoi as above.

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

Solution: Clearly, H₁ = 1.

Consider top (n–1) discs. We can move these discs to the middle peg using

H_n–1 moves. The n^th 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 H_n–1 moves. Thus, total number of moves needed to move n discs are: H_n = 2H_n–1 + 1. Hence the recurrence relation for the Tower of Hanoi is:

H_n = 1 if n = 1.

H_n = 2H_n–1 + 1 otherwise.