Mathematical Induction & Tower of Hanoi

Mathematical Induction and Recurrence Relations

Mathematical induction is an indispensable proof technique in algorithm design and analysis. It is used to prove that a property $P(n)$ holds for all positive integers $n \ge n_0$ .

The Principle of Mathematical Induction

Basis Step (Base Case): Verify that $P(n_0)$ is true (usually for $n_0 = 1$ or $0$ ).
Inductive Hypothesis: Assume that $P(k)$ is true for an arbitrary integer $k \ge n_0$ .
Inductive Step: Prove that if $P(k)$ is true, then $P(k+1)$ must also be true:

P(k) \implies P(k+1)

By mathematical induction, $P(n)$ is true for all integers $n \ge n_0$ .

Case Study: The Tower of Hanoi

The Tower of Hanoi is a classic algorithmic puzzle designed by French mathematician Édouard Lucas in 1883.

Problem Definition & Constraints

You are given three pegs: Source ( $A$ ), Auxiliary ( $B$ ), and Destination ( $C$ ), along with $n$ disks of distinct sizes initially stacked on Peg $A$ in decreasing order of size (largest at the bottom).

Goal: Move all $n$ disks from the source peg ( $A$ ) to the destination peg ( $C$ ).
Constraints:
1. Only one disk may be moved at a time.
2. Only the top disk on any peg can be removed and transferred.
3. No larger disk may ever be placed on top of a smaller disk.

Diagram loads as you scroll.

Recursive Algorithm

Hanoi(n, source, auxiliary, destination):
    if n == 1 then:
        move disk 1 from source to destination
        return

    // Step 1: Move top n-1 disks from source to auxiliary
    Hanoi(n - 1, source, destination, auxiliary)

    // Step 2: Move the largest disk directly to destination
    move disk n from source to destination

    // Step 3: Move the n-1 disks from auxiliary to destination
    Hanoi(n - 1, auxiliary, source, destination)

Step-by-Step Move Tracing

3-Disk Trace ( $n = 3$ , Minimum Moves $= 2^3 - 1 = 7$ )

Move #	Disk	From Peg	To Peg	State After Move $(A, B, C)$
0	-	-	-	$A = [3, 2, 1], B = [], C = []$
1	Disk 1	$A$	$C$	$A = [3, 2], B = [], C = [1]$
2	Disk 2	$A$	$B$	$A = [3], B = [2], C = [1]$
3	Disk 1	$C$	$B$	$A = [3], B = [2, 1], C = []$
4	Disk 3	$A$	$C$	$A = [], B = [2, 1], C = [3]$
5	Disk 1	$B$	$A$	$A = [1], B = [2], C = [3]$
6	Disk 2	$B$	$C$	$A = [1], B = [], C = [3, 2]$
7	Disk 1	$A$	$C$	$A = [], B = [], C = [3, 2, 1]$

4-Disk Trace ( $n = 4$ , Minimum Moves $= 2^4 - 1 = 15$ )

Move #	Disk	Action	Description
1	Disk 1	$A \to B$	Move disk 1 out of the way
2	Disk 2	$A \to C$	Move disk 2
3	Disk 1	$B \to C$	Stack disk 1 on 2
4	Disk 3	$A \to B$	Move disk 3 to peg $B$
5	Disk 1	$C \to A$	Unstack disk 1
6	Disk 2	$C \to B$	Stack disk 2 on 3
7	Disk 1	$A \to B$	Subproblem $n=3$ to peg $B$ complete
8	Disk 4	$A \to C$	Largest disk 4 moves to final destination $C$
9	Disk 1	$B \to C$	Begin transferring $n=3$ from $B$ to $C$
10	Disk 2	$B \to A$	Move disk 2
11	Disk 1	$C \to A$	Stack disk 1 on 2
12	Disk 3	$B \to C$	Move disk 3 to $C$
13	Disk 1	$A \to B$	Unstack disk 1
14	Disk 2	$A \to C$	Stack disk 2 on 3
15	Disk 1	$B \to C$	All 4 disks successfully on destination peg $C$

Recurrence Relation and Proof

Let $M(n)$ be the number of moves needed for $n$ disks. From the recursive algorithm:

M(n) = 2 M(n - 1) + 1 \quad \text{for } n > 1, \quad M(1) = 1

Solving by Backward Substitution

\begin{aligned} M(n) &= 2 M(n-1) + 1 \\ &= 2 [2 M(n-2) + 1] + 1 = 2^2 M(n-2) + 2 + 1 \\ &= 2^2 [2 M(n-3) + 1] + 2 + 1 = 2^3 M(n-3) + 2^2 + 2^1 + 2^0 \\ &\ \ \vdots \\ &= 2^{n-1} M(1) + \sum_{i=0}^{n-2} 2^i = 2^{n-1} (1) + (2^{n-1} - 1) = 2^n - 1 \end{aligned}

Proof by Mathematical Induction

Base Case ( $n = 1$ ): $M(1) = 2^1 - 1 = 1$ . The formula holds.
Inductive Hypothesis: Assume $M(k) = 2^k - 1$ for some integer $k \ge 1$ .
Inductive Step: Show $M(k+1) = 2^{k+1} - 1$ :

\begin{aligned} M(k+1) &= 2 M(k) + 1 \\ &= 2(2^k - 1) + 1 \quad \text{(by inductive hypothesis)} \\ &= 2^{k+1} - 2 + 1 \\ &= 2^{k+1} - 1 \end{aligned}

Thus, the formula holds for $k+1$ . By induction, the minimum number of moves for $n$ disks is exactly $2^n - 1 \in \Theta(2^n)$ .

Time Complexity: $\Theta(2^n)$
Space Complexity (Recursion Depth): $\Theta(n)$

Exercises

Exercise 1

If a computer can execute $10^9$ moves per second, how long would it take to solve the Tower of Hanoi for $n = 64$ disks?

Show solution ↓

Solution

Total moves required:

2^{64} - 1 \approx 1.84467 \times 10^{19} \text{ moves}

Time in seconds:

\frac{1.84467 \times 10^{19}}{10^9} \approx 1.84467 \times 10^{10} \text{ seconds}

Converting to years ( $1 \text{ year} \approx 3.1536 \times 10^7 \text{ s}$ ):

\text{Time} \approx \frac{1.84467 \times 10^{10}}{3.1536 \times 10^7} \approx 584.9 \text{ years}

Even at 1 billion moves per second, it would take over 584 years!

Exercise 2

Prove by mathematical induction that for all $n \ge 1$ :

1 + 3 + 5 + \dots + (2n - 1) = n^2