有趣的遞推數列問題

摘要本文我們將闡述遞推關系的有關定義及其相關概念，將這些內容作分類分步介紹，并給出相關的一系列例題及其解法。

關鍵詞遞推 Fibonacci數列 梵塔之謎 染色

中圖分類號:G633.6文獻標識碼:A

談到遞推關系， Fibonacci數列最具典型性。中世紀意大利數學家斐波那契在1202年提出了這樣一個問題(統稱兔子繁殖問題):“年初在圍欄中放了一對小兔，每對新生的小兔從第二個月開始生一對小兔，求一年后，圍欄里的兔子的對數。”通過分析不難得到每個月的兔子對數構成了1，1，2，3，5，8，13，……這樣一個遞推數列，用遞推方法建立數列的通項，是數學中最有用的方法之一。我們來看幾個常見的遞推關系例子。

1 梵塔之謎

有3個竹樁，把n個大小互異的圓盤由大到小穿在第一個竹樁上，最大的在底部，現在打算一個一個地搬動，從第一竹樁全部轉移到另一個竹樁上，并且要求任何時候都不允許把大圓盤放在較小圓盤的上面。問:至少搬動幾次才能完成這個轉移?設把A柱上的n片圓片全部轉移到C柱所需的最少次數為an，試回答:(1)a1，a2，a3是多少?(2)an和an-1間有怎樣的關系?(3)求an。

解:(1)顯然A柱上只有一個圓片時，只需移動一次，就可以將圓片移到C柱。所以a1=1 。

當A柱上有兩片圓片時，必須利用B柱作過渡，即先將第一片移到B柱，再將第二片移到C柱，最后將B柱上的小圓片移到C柱上。這樣，A柱上的兩片圓片就移到了C柱上，并且小片壓在大片上。因此，a2=3 。

當A柱上有三片圓片時，應該怎樣考慮呢?由于必須一片一片的移動，大的又不許壓在小的上面，所以，想要移動A柱上最底下的一片圓片，也就是第三片圓片，就必須將第一、二片圓片先搬到某一根柱上(當然是搬到B柱上比較恰當; 注意，這需要用a2=3次)，這樣一來，就可以將第三片圓片從A柱上移到C柱上(這樣又是1次)。最后，將B柱上的兩片圓片通過A柱過渡到C柱上(這樣又要a2=3次)。所以，一共要7次，即:a3=2a2+1。

(2)從第(1)小題的討論中，不難知道an與an-1間的關系，應是an=2an-1+1是一個常系數線性非齊次遞推關系，下面用升階法求解這個遞推關系。

(3)因為an=2an-1+1，an-1=2an-2+1。兩式相減得:an-an-1=2(an-1-an-2)，同理，有an-1-an-2=2(an-2-an-3)，an-2 -an-3=2(an-3- an-4)……，a3-a2=2(a2-a1)，迭代得 :an-an-1=2n-2(a2-a1).又因a1=1，a2=3 所以an-an-1=2n-1，累加得an-a1=2+22+…… +2n-1，即an=1+2+22+ …… +2n-1=2n-1

2 染色問題

設有n個頂點V1，V2，…VN和n條L1L2…LN邊構成一個回形圖，用七種顏色對每個點著色，使每兩個有邊相連的頂點著不同的顏色，問這種著色法共有多少種:

解:設著色法數為(與頂點數n有關)，為研究問題方便起見，我們在回形圖中去掉一條邊，例如Vn和V1之間的邊，則此圖變為有兩個端點的一條直線。

在直線圖中，V1有七種顏色，V1一旦選定顏色后，V2只有六種著色法，V2選定后，V3仍有六種著色法，因為V3 與V1無邊直接相連，可以著相同的顏色，如此下去，回形圖的著色法共有種，直線圖的所有著色法可分為兩類:一類是V1 與Vn著不同的顏色;另一類是V1與Vn著相同的顏色。

前者就是G的著色數，后者相當于把V1，Vn合為一個點，構成n-1個點的回路著色法數，由此可知，(n=3、4、…)。不難得出，(種)，可以用遞推法求。，將代入得:(n=2、3、4、…)，則即為著色數。

3 分形問題

有一個雪花序列，其產生規則是:將正三角形k0的每一邊三等分，而以其居中的那一條線段為一底邊向外作等邊三角形，再擦去中間的那條邊，便得到第一條雪花曲線K1;再將K1的每條邊三等分，并重復上述作法，便得到第二條雪花曲線K2;……;把KN-1的每條邊三等分，并以中間那條邊向外作等邊三角形，再擦去中間的那條邊，便得到第n條雪花曲線KN(n=1，2，3，……)。①設K0的周長為L0，即正三角形周長，求第n條雪花曲線KN的周長LN;②設K0的面積為A0，即正三角形面積，求第n條雪花曲線KN圍成的面積AN;③隨著n的增大，LN和AN是否會各趨向于某一定值?

解:①雪花曲線序列中，后一雪花曲線的長為相鄰前一個長的。設第n條雪花曲線的長為LN，則LN=()NL0，n=1，2，3，…

② KN比KN-1多3·4N-1(KN-1的邊數)個面積為的正三角形。因而，AN=AN-1+3·4N-1·，AN=[8-3()N]。

③由于LN=()NL0是公比為>1的等比數列，所以LN趨向于無窮大;另一方面，AN= [8-3()N]，而0<<1，所以AN將會趨向于定值A0。

注:(1)本題的結論十分有趣，無限長的曲線居然只能圍成有限大的面積，出人意料。這是現代數學一個新的分支——“分形幾何學”的一個簡單例子。(2)美麗的雪花曲線是瑞典數學家H.vonKonch在1904年首次發現的，故又稱之為Koch曲線。