Question

There is a famous puzzle called the Towers of Hanoi that consists of three pegs

and n circular disks, all of different sizes. The disks start on the leftmost peg, with the largest disk

on the bottom, the second largest on top of it, and so on, up to the smallest disk on top. The goal

is to move the disks so that they are stacked in this same order on the rightmost peg. However,

you are allowed to move only one disk at a time, and you are never able to place a larger disk on

top of a smaller disk. Let t_n denote the fewest moves (a move being taking a disk from one peg

and placing it onto another) in which you can accomplish the goal. Determine an explicit formula

for t_n.

Answer 1

is the number of steps required with n+1 disk

To do this, we must first move all the top n disk (except that last n+1 th largest disk) onto the middle peg

This can be done in moves

Then we move the largest disk from the left-most to the right-most peg (so +1 moves)

And then finally, we move the disks on the middle peg onto the right-most peg

This can again be achieved in moves

So total number of moves is

And so we have the recurrence relation with

So we have

Notice these are all one smaller than a power oof 2

So the explicit formula is is the required number of steps

Hope this was helpful. Please do leave a positive rating if you liked this answer. Thanks and have a good day!