1.
(a)
What is the smallest number of moves required to transport 2 disks to another pillar?
(b)
What is the smallest number of moves required to transport 3 disks to another pillar?
(c)
What is the smallest number of moves required to transport 4 disks to another pillar?
(d)
To find the smallest number of moves required to transport 5 disks to another pillar, let’s try to relate this task to the task of moving 4 disks. How many moves do each of the following tasks require?
- Move the 4 smallest disks to the second pillar: moves.
- Move the largest disk to the third pillar: moves.
- Move the 4 smallest disks to the third pillar (on top of the largest disk): moves.
Therefore, the smallest number of moves required to move five disks is:
(e)
Generalize the last observation. Let \(a_n\) represent the smallest number of moves required to transport \(n\) disks from the start pillar to another pillar. Then \(a_{n-1}\) represents the number of moves required to transport \(n-1\) disks to another pillar.
Give a formula for \(a_{n}\) in terms of \(a_{n-1}\text{.}\)
\(a_n =\).
