There are four towers who is named A,B,C,D respectively.
Initially there are n disks. All disks are different in size.
The disks are initially stacked on tower A increasing in size from the top to the bottom.
You can't put disk A onto disk B if the size of disk A is bigger than the size of disk B.
The goal is to transfer all of the disks from tower A to tower D with smallest amount of options.
Above all is the description of the problem.
The solution uses $$$f(n)$$$ to represent the minimum times to transfer n disks increasing in size from the top to the bottom from tower A to tower D. And it uses $$$d(n)$$$ to represent the minimum times to transfer n disks increasing in size from the top to the bottom from tower A to tower C without the help of tower D (It means you can't stack disks on tower D).
Then the solution claims that $$$f(n) = min(2 \times f(i) + d(n - i)) (1 \le i \lt n)$$$, but I don't know why. Please give me a proof,thanks!








