Lecture on Towers of Hanoi: Recurrence Relation of Moves

Overview

In this lecture, we will learn how to write the recurrence relation for the number of moves needed to solve the Towers of Hanoi problem. This will provide us with the formula to determine the number of moves required to transfer n disks from one peg to another.

Key Topics

• Understanding the Algorithm: Reviewed the Towers of Hanoi algorithm and confirmed its capability to solve the problem of moving disks between pegs.
• Defining the Recurrence Relation: Derived the recurrence relation for calculating the moves:
  • Base Case: If ( n = 1 ), ( m(n) = 1 )
  • Recursive Case: ( m(n) = 2 \cdot m(n-1) + 1 ) for ( n > 1 )

Recurrence Relation Calculation

• Apply the substitution method to find the formula:
  • Assume ( m(n) = 2 \cdot m(n-1) + 1 )
  • Substitute recursively and simplify to find the explicit formula for ( m(n) ).

Formula

• Formula Derived: ( m(n) = 2^n - 1 )
• This formula represents the number of moves needed for n disks.
• Observes exponential growth in the number of moves needed with an increase in n.

Examples

1. For 1 Disk: ( m(1) = 1 )
2. For 2 Disks: ( m(2) = 3 )
3. For 3 Disks: ( m(3) = 7 )
4. For 10 Disks: ( m(10) = 1023 )
5. For 30 Disks: ( m(30) = 1,073,741,823 ) (nearly 1 billion moves, taking roughly 32 years if one move is made per second)

Conclusion

• The Towers of Hanoi problem illustrates the exponential growth in required moves with increased disks.
• The solution formula ( 2^n - 1 ) is derived through the substitution method.
• The problem is a classic example of exponential problem-solving complexity, especially highlighted with larger numbers of disks.

Thank you for watching this presentation. See you in the next lecture.