高一 遞迴數列 求一般項

兩種方法各有好處 方法二比較抽象 但是學到一個新方法應該是不錯的事

例如 a(1)=a(2)=1,a(n+2)=a(n)+a(n+1)稱為費氏數列

有多種方法可以求一般項a(n) 其中 製造新數列就是方法之一

---

河內塔問題 故事是這說的

婆羅痆斯國(今印度北部瓦臘納西(Varanasi)，靠近尼泊爾)方圓四千多里，居民大多信奉外道，少數人敬信佛法。

從婆羅痆河向東走十多里，就到了鹿野苑，是釋迦牟尼佛初轉法輪的地方。

寺院內精舍西南有一座石塔，塔前有無憂王石柱，石柱旁邊不遠處有座佛塔，是當初阿若憍陳如等五人見如來放棄苦行，便不再侍衛如來而來這裡自己修行的地方。

旁邊還有三座塔，有過去三佛安坐和散步的遺跡。      大唐西域記 商周出版 p.144

 

維斯瓦納特(Kashi Vishwanath)是印度濕婆神(大自在天)的寺廟，位於瓦臘納西。

廟裡面有一個很大的房間，裡面有3根柱子，旁邊放了64個金屬圓盤。

依照下列規則移動圓盤：

 

有A,B,C三柱，其中A柱上套著 個大小不同的圓盤，

將其由小到大圓盤編號為1，2，……, 。若藉助A、B、C三柱作橋樑，且每次移動圓盤時都保持較大圓盤在下面，較小圓盤放在上面的規定，

將A柱的圓盤全部移動到C柱。

假設n個圓盤從A搬到B(或者C)至少需要a(n)次(依照以上規則) 則

1. 先把上面n-1個圓盤搬到B(需要a(n-1)次)
2. 再把A上最大的圓盤搬到C(搬1次)
3. 再把B上n-1個圓盤搬到C(需要搬a(n-1)次)

 所以a(n)=2a(n-1)+1,a(1)=1

這就是前面所提的數列 求a(n)

一旦工作完成，這個世界終將結束。

假設移動一個圓盤需要1分鐘，則64個圓盤依照上述規則，由A柱全部移動的C柱需要多少時間？世界何時毀滅？

以上所述，盧卡斯(Édouard Lucas 1842~1891)在1887年把它寫成一個趣味數學遊戲(8個圓盤的情形)又稱為河內(Hanoi)塔問題。

1. 遞迴數列與不動點
2. 利用生成函數解遞迴數列
3. 約瑟夫問題
4. Martin Gardner 趣味數學 p.62

---