問題詳情:
古代印度婆羅門教寺廟內的僧侶們曾經玩過一種被稱爲“河內寶塔問題”的遊戲,其玩法如下:如圖,設有n()個圓盤依其半徑大小,大的在下,小的在上套在A柱上,現要將套在A柱上的盤換到C柱上,要求每次只能搬動一個,而且任何時候不允許將大盤套在小盤上面,假定有三根柱子A、B、C可供使用.
現用an表示將n個圓盤全部從A柱上移到C柱上至少所需要移動的次數,回答下列問題:
(I)求a1,a2,a3,並寫出an的一個遞推關係;
(II)記,求和();
(提示:)
(III)*:.
【回答】
解:(1) ………2分
事實上,要將個圓盤全部轉移到C柱上,只需先將上面個圓盤轉移到B柱上,需要次轉移,然後將最大的那個圓盤轉移到C柱上,需要一次轉移,再將柱上的個圓盤轉移到C柱上,需要次轉移,所以有 ………4分
(II)由(1)得:,
所以 …………6分
…………9分
(III)(II)得:
令,則當時
又,所以對一切有:
…………12分
(方法二:,從第四項開始放縮求和)
另方面恆成立,所以對一切有
綜上所述有:…
知識點:數列
題型:解答題