Towers of Hanoi, continued

When you solved the Towers of Hanoi for three disks, you needed to expose the bottom disk, disk $3$, so that you could move it from peg A to peg B. In order to expose disk $3$, you needed to move disks $1$ and $2$ from peg A to the spare peg, which is peg C:

Wait a minute—it looks like two disks moved in one step, violating the first rule. But they did not move in one step. You agreed that you can move disks $1$ and $2$ from any peg to any peg, using three steps. The situation above represents what you have after three steps. (Move disk 1 from peg A to peg B; move disk $2$ from peg A to peg C; move disk $1$ from peg B to peg C.)

More to the point, by moving disks $1$ and $2$ from peg A to peg C, you have recursively solved a subproblem: move disks $1$ through $n-1$ (remember that $n = 3$) from peg A to peg C. Once you've solved this subproblem, you can move disk $3$ from peg A to peg B:

Now, to finish up, you need to recursively solve the subproblem of moving disks $1$ through $n-1$ from peg C to peg B. Again, you agreed that you can do so in three steps. (Move disk $1$ from peg C to peg A; move disk $2$ from peg C to peg B; move disk $1$ from peg A to peg B.) And you're done:

And—you knew this question is coming—is there anything special about which pegs you moved disks $1$ through $3$ from and to? You could have moved them from any peg to any peg. For example, from peg B to peg C:

• Recursively solve the subproblem of moving disks $1$ ...