有趣的遞推數(shù)列問(wèn)題

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

關(guān)鍵詞遞推 Fibonacci數(shù)列 梵塔之謎 染色

中圖分類(lèi)號(hào):G633.6文獻(xiàn)標(biāo)識(shí)碼:A

談到遞推關(guān)系， Fibonacci數(shù)列最具典型性。中世紀(jì)意大利數(shù)學(xué)家斐波那契在1202年提出了這樣一個(gè)問(wèn)題(統(tǒng)稱(chēng)兔子繁殖問(wèn)題):“年初在圍欄中放了一對(duì)小兔，每對(duì)新生的小兔從第二個(gè)月開(kāi)始生一對(duì)小兔，求一年后，圍欄里的兔子的對(duì)數(shù)?！蓖ㄟ^(guò)分析不難得到每個(gè)月的兔子對(duì)數(shù)構(gòu)成了1，1，2，3，5，8，13，……這樣一個(gè)遞推數(shù)列，用遞推方法建立數(shù)列的通項(xiàng)，是數(shù)學(xué)中最有用的方法之一。我們來(lái)看幾個(gè)常見(jiàn)的遞推關(guān)系例子。

1 梵塔之謎

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

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

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

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

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

(3)因?yàn)閍n=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 染色問(wèn)題

設(shè)有n個(gè)頂點(diǎn)V1，V2，…VN和n條L1L2…LN邊構(gòu)成一個(gè)回形圖，用七種顏色對(duì)每個(gè)點(diǎn)著色，使每?jī)蓚€(gè)有邊相連的頂點(diǎn)著不同的顏色，問(wèn)這種著色法共有多少種:

解:設(shè)著色法數(shù)為(與頂點(diǎn)數(shù)n有關(guān))，為研究問(wèn)題方便起見(jiàn)，我們?cè)诨匦螆D中去掉一條邊，例如Vn和V1之間的邊，則此圖變?yōu)橛袃蓚€(gè)端點(diǎn)的一條直線。

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

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

3 分形問(wèn)題

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

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

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

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

注:(1)本題的結(jié)論十分有趣，無(wú)限長(zhǎng)的曲線居然只能?chē)捎邢薮蟮拿娣e，出人意料。這是現(xiàn)代數(shù)學(xué)一個(gè)新的分支——“分形幾何學(xué)”的一個(gè)簡(jiǎn)單例子。(2)美麗的雪花曲線是瑞典數(shù)學(xué)家H.vonKonch在1904年首次發(fā)現(xiàn)的，故又稱(chēng)之為Koch曲線。