Detour: The Towers of Hanoi

The Towers of Hanoi puzzle consists of three vertical pegs and a number of disks of different sizes, each with a hole in its center so that it fits on the pegs. The disks are initially stacked on the left peg (peg 1) so that disks increase in size from the top down. The puzzle is played by moving one disk at a time between pegs, with the goal of moving all disks from the left peg (peg 1) to the right peg (peg 3). However, you’re not allowed to place a disk on top of a smaller disk.

STOP and Think: What is the minimum number of steps needed to solve the Towers of Hanoi Problem for three disks?

Steps required to solve the Towers of Hanoi problem

Let’s see how many steps are required to solve the Towers of Hanoi Problem for four disks. The first important observation is that sooner or later, you’ll have to move the largest disk to the right peg. However, in order to move the largest disk, we first have to move all three smallest disks off the first peg. Furthermore, these three smallest disks must all be on the same peg because the largest disk can’t be placed on top of another disk. Thus, we first have to move the top three disks to the middle peg (7 moves), then move the largest disk to the right peg (1 move), then again move the three smallest disks from the middle peg to the top of the largest disk on the right peg (another 7 moves), for a total of 15 moves.

Minimum steps required

More generally, let T(n) denote the minimum number of steps required to solve the Towers of Hanoi puzzle with $n$ ...