The recurrence relation capturing the optimal execution time of the Towers of…

Key insight: the recursive algorithm moves n−1 disks, then the largest disk, then n−1 disks again.

• Step 1: Move the top n−1 disks to the auxiliary peg — cost T(n−1).

• Step 2: Move the largest disk to the target peg — cost 1.

• Step 3: Move the n−1 disks from the auxiliary peg onto the largest disk — cost T(n−1).

Combining these costs gives the recurrence T(n) = 2T(n−1) + 1.

With the base case T(0) = 0 (no disks, no moves), this recurrence solves to T(n) = 2^n − 1, the minimum number of moves required.