Recurrence relation for Tower of Hanoi

The Tower of Hanoi is one of the most popular puzzle of the nineteenth century. It consists of three pegs mounted on a board together and consists of disks of different sizes. At first, all the disks are kept on one peg(say peg 1) with the largest peg at the bottom and the size of pegs gradually decreases to the top.
Goal:- The goal of this puzzle is to transfer all the disks from one peg to another in order of size, placing the largest one at the bottom.
Rule:- The rule of the puzzle is that we can move a disk from one peg to another as long as the disk is never placed on the top of the smaller one.

Recurrence relation

Finding a recurrence relation:
Let us consider there are n disks on peg 1. Let, H(n) denotes the number of moves required to solve the puzzle. The initial position is shown in the upper part of the figure. We can transfer the top n-1 disks from peg 1 to peg 3 as shown in the bottom part of the figure. Clearly, this process will take H(n-1) moves. It is because the disks arrangement as shown in the last figure is an instance of the original problem with n-1 disks. And in recurrence relation, the solution is expressed in terms of one or more previous terms of the sequence. Then, the larger disk on peg 1 can be moved to peg 2 with a single move. We can transfer the disks on peg 3 to peg 2 with additional H(n-1) moves placing them on the top of the larger disk.

The recurrence relation then becomes,
             H(n) = 2 * H(n-1) + 1
Here, the initial condition is H(1) = 1 which is obvious.

Now, we can use an iterative approach to solve it.
H(n) = 2 * H(n-1) + 1
        = 2 * (2 * H(n-2) + 1) + 1 = 22 * H(n-2) + 2 + 1
        = 22 * (2 * H(n-3) + 1) + 2 + 1 = 23 * H(n-3) + 22 + 2 + 1
        …   …   …
        = 2n-1 * H(1) + 2n-2 + 2n-3 + … + 2 + 1
        = 2n-1 + 2n-2 + 2n-3 + … + 2 + 1                                                    (since, H(1) = 1)
        = 1 + 2 + … + 2n-3 + 2n-2 + 2n-1     (Using sum of geometric sequence=(a*(rn – 1)) / (r-1) )
        = 2n – 1                                        (Here, a = 1, r = 2 and n = number of terms)
i.e., H(n) = 2n – 1


The formula that we have derived can also be verified using mathematical induction as
P(n):  H(n) = 2n – 1
Basis step: P(1): H(1) = 2 - 1 = 1 , which is true.
Inductive step: Let, P(k) is true. i.e., H(k) = 2k – 1
                        Now, we have to show that P(k+1) is true.

                        So, P(k+1):H(k+1) = 2 * H(k) + 1
                                                      = 2 * (2k – 1) + 1
                                                      = 2k+1 – 1
Hence, the formula has also been verified by mathematical induction.

Comments

Post a Comment

Popular posts from this blog

Binary Search

Image
Binary search is used to locate an element in an array efficiently than the linear search. To use a binary search, the array must be sorted in non-decreasing order. If T[1…n] is the sorted array, then the binary search returns an index i at which the element(say x) is found. If the element is not in the array then, it returns a possible index where the element might be inserted. Here, we wish to find the index i such that 1 < i < n + 1 and T[i - 1] < x < T[i]. At first, let’s see how do we locate an element in an array using linear or sequential approach. LINEAR-SEARCH (T[1…n], x) for i = 1 to n if T[i] > x return i return n + 1 From the above algorithm, we can see clearly that the algorithm takes the time in θ(n) in the worst case where n is the number of elements. Now, let’s see how binary search algorithm will improve this running time. Basically, a binary search algorithm works like this. First, we compare the element x with the middle element of...
Read more

System Bus

Image
Have you ever wondered how the microprocessor communicates with the devices connected to it? Well, there are a group of wires (communication path) between microprocessor and its peripherals (and memory) to carry bits which are known as system bus. The system bus performs the following steps to communicate with the peripheral: i.         Identify the peripheral or the memory location (with its address). ii.       Transfer data and instructions in the form of bits. iii.     Provide timing and synchronization signals. According to the above functions, system bus can be classified into three types which are described below: Address Bus: It is a set of wires that is used to transmit address from the microprocessor to its peripheral devices (or memory. It is unidirectional. Each peripheral or memory is identified by its address. This is similar to the postal address of the house. For example...
Read more

Differences between hardwired and micro-programmed control unit

S.N. Hardwired Control Unit Micro-programmed Control Unit 1. It is implemented through the use of sequential logic circuit. Its input logic signals are transformed into a set of output logic signals which are control signals. It is implemented through the use of micro-programs. Micro-programs (control information) are organized as a sequence of micro-instructions stored in a special control memory. 2. This design uses a fixed architecture so, it require changes in wiring if the instruction set is modified. It is easy to reconfigure and modify instruction set. 3. It is difficult to build a circuit that satisfies all the operations. It is simple in structure. 4. It has faster mode of operation. It is comparatively slower. 5. It is comparatively expensive. It is cheaper. 6. It is preferred for less number of instruction sets. I...
Read more