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. 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 arrangemen...