申論題

2. 河內塔(Tower of Hanoi)問題為一有趣之數學遊戲，如右圖所示，有 A, B, C 三柱，其中 A 柱上套著 n 個大小不同的 圓盤，將其由小到大圓盤編號為 1, 2, …, n。若藉助 A, B, C 三柱作橋樑，且每次只能移動一個圓盤，都保持較大圓 盤在下面、較小圓盤在上面的規定，將 A 柱的圓盤全部移動到 C 柱。設 an 表示將 n 個圓盤全部由 A 柱搬到 C 柱所 需的最少次數，試求(1)＜a_n＞的遞迴關係式，(2)a_n。 (4 分) 5