In Class: The Tower of Hanoi

Learning Objectives

You will formulate a simple recursive algorithm to solve a puzzle.
You will use recurrence relations and proof by induction to describe the runtime of your algorithm.

Introduction

In the classic puzzle of the Tower of Hanoi, you start with a stack of disks on one of three pegs. The disks are stacked by size: largest at the bottom, smallest at the top:

The challenge is to move the complete stack from one peg to another, subject to the following rules:

You can move one disk at a time from one peg to another. You can choose which peg to move to. For example, in the initial configuration, the topmost disk can move to the second peg or the third.
A larger disk can never be on top of a smaller disk.

Part A

On a device of your choosing, navigate to this website on which you can play the Tower of Hanoi. Then, play with two, three, and four disks.

Part B

Describe an algorithm for solving the Tower of Hanoi with \(n = 1\) disk. Don’t overthink it!

Part C

Imagine now that you had an algorithm for solving the Tower of Hanoi with \(n = k\) disks. How could you use this algorithm to solve the Tower of Hanoi with \(n = k+1\) disks?

Hint: first move the top \(k\) disks to another peg using your algorithm.

Part D

Let \(t_n\) be the minimum number of moves necessary to solve the Tower of Hanoi problem with \(n\) disks. The sequence \(t_n\) satisfies a recurrence relation of the form

\[ t_{n+1} = at_n + b \]

with initial condition \(t_1 = c\) for some \(a, b, c \in \mathbb{Z}\).

Using your response from Parts B and C, fill in the values of \(a\), \(b\), and \(c\).

Part E

Compute \(t_2\), \(t_3\), \(t_4\), and \(t_5\) by hand.

Part F

The sequence \(t_n\) has closed-form solution

\[ t_n = d^n + e \]

for some \(d, e \in \mathbb{Z}\). Using your response from Part E, guess the values of \(d\) and \(e\).

Part G

Write a proof by induction that your closed-form solution from Part F is indeed a solution to the recurrence relation from Part D.