數列的遞迴定義及其應用  沈源培老師

數列{an}: a1, a2, a3,…an,… , 其中an稱為數列的一般項或第n項,而an為n

的函數f(n),即為“該數列的數值所呈現的規律”

【例】等差數列: 1, 4, 7, 10,…; 其一般項為3n-2 ,我們以{3n-2}表之

【例】等比數列: 2, 4, 8, 16,…; 其一般項為2n ,我們以{2n}表之

但我們並不一定以“該數列的數值所呈現的規律”表示數列{an}的特性,

而以“該數列的前後項的關係”表之.

【例】以{an}: a1=1 ,an+1=an+3 ("nÎN) 表等差數列: 1, 4, 7, 10,……

【例】以{an}: a1=2 ,an+1=2an ("nÎN) 表等比數列: 2, 4, 8, 16,……

這種確認{an}前後項的關係來定義數列{an}的方式稱為“遞迴定義”

 

【例】數列{an}定義如右:a1=1, an+1=(n+1)an ("nÎN), 則

a1=1, a2=2×1, a3=3×2×1, a4=4×3×2×1, a5=5×4×3×2×1,……,得一般項

an=n×(n-1)×(n-2)×…×3×2×1=n! ("nÎN) ;我們稱數列{an}為階乘函數數列

{n!}: 1!=1 , (n+1)!=(n+1)×n!

 

【例】設數列{an}的遞迴定義是a1=1, an+1=an+(n+1)2 ("nÎN), 則

an-an-1 = n2, an-1-an-2 = (n-1)2, an-2-an-3 = (n-2)2,……a2-a1 = 22,得一般項

 

【例】設數列{an}定義如右: a1=1 ,an+1=a1+a2+…+an ("nÎN) ,則

a3-a2=a1=a2, a4-a3=a2+a1=a3, a5-a4=a3+a2+a1=a4, ……得

an-an-1=an-2+…+a1= an-1 ,即an=2an-1 (n³3) ; a2=1 ,a1=1,得一般項

a1=1 ,an=2n-1 (n³2)

 

當然,『如何由數列的遞迴定義式求得一般項an=f(n)?』是“遞迴定義”

單元的主題之一; 但此處更強調它是探索數列問題的另一種切入點:

『先嘗試找尋數列前後項的關係,從而求得數列的一般項.』

以下我們透過一些著名問題的介紹,闡明其精髓所在

 

【問題研究】雪花碎形   (Helge von koch (1870-1924)提出)

設T1,T2,…Tn……為一系列多邊形,其作法如下:T1為邊長1的正三角形;以

Tn每一邊中間三分之一的線段為一邊向外作正三角形,然後將該三分之一

的線段抹去所得多邊形Tn+1, n=1,2,3,4L (如圖示) ;令Tn的周長Sn,面積An,

則我們將發現:Sn=¥,而An存在, 即得出一個具無限周長卻圍出有限

面積的曲線¾KOCH曲線

【解說】其實Tn+1是由Tn每一邊直線段       轉變成折線段      所構成

 

 

 

 

 

 

 

 

 

【問題研究】平面上過定點A的n個圓最多將平面分割成多少區域?

 

 

 

 

 

【問題研究】古印度梵天塔 (Tower of Brahma) 的傳說

天地初開,大梵天在Benares神殿裡,豎立三根柱子,而將六十四個大小不同

的金圈“由大而小,由下而上”在其中一根柱子上堆疊,祂並諭示世界末日

的預言:『一次搬移一個地將全部金圈移至另一根柱子,又搬移過程中,需遵

守“大金圈不得在小金圈之上”的戒律,而完成之時,因緣俱散,一切將灰飛

煙滅!』

 

 

 

 

 

【問題研究】今有樓梯梯階8階,某人上樓每步跨一階或二階,則上樓的方法

              有多少種?

 

 

 

 

 

【問題研究】 Leonardo Fibonacci (A.D 1170~1250) 提出一個有趣的問題

已知兔子出生後經兩個月就能生小兔, 若每次恰好生下一對(一雌一雄)兔

子.假使養了一對(一雌一雄)初生的兔子,試問一年後共有多少對兔子?

(假設生下的兔子均長生不死)

 

 

 

 

 

【問題研究】將n封不同的信L1,L2,LLn分別裝入寫著n個收信人姓名、地

             址的信封E1,E2LEn,則每封信都裝錯信封的情形有多少種?

Nicolaus Bernoulli (1695~1726) 所提出而被Leonhard Euler (1707~1783) 稱為

組合數學中的一個奇妙問題.

 

 

 

 

 

【問題研究】(Markov chain機率問題)

設A,B二箱中,A箱內有兩球,一黑一白, B箱內有一白球.甲,乙二人輪流取

球,每次先由甲自A箱任取一球,放入B箱內,再由乙自B箱任取一球,放入

A 箱,這樣稱為一局. 那麼當第一局結束時,A箱內兩球為一黑一白的機率

為     .當第三局結束時, A箱內兩球為一黑一白的機率為     .

 

 

 

 

 

 

【問題研究】

有一人流浪A,B,C,D四鎮間, 此四鎮相鄰關係如右圖,假設每日  A       B

清晨,此人決定當日夜晚留宿該鎮,或改而前往相鄰任一鎮之機率

為. 若此人第一夜宿於A鎮,則第三夜亦宿於A鎮之機率為    D        C

     ;而第五夜此人宿於A鎮之機率為    , 宿於B鎮之機率為     .

 

 

 

 

 

【問題研究】(期望值)

甲、乙兩袋,甲袋有紅球1個,黑球3個,乙袋有紅球,黑球各2個,.今自甲

袋中任取一球,放入乙袋,再自乙袋任取一球,放回甲袋. 設如此操作經n

次後,甲袋中紅球數的期望值為En, 試求En=?

 

 

 

 

 

結語:

遞迴定義是數列表示的一種方式,更是處理問題的另一種切入點. 當我們

處理「過定點的n個圓最多將平面分割成多少區域?」的問題時,若直接指

向“過定點的n個圓如何才能將平面分割成最多區域?”思考時,則問題不

易處理, 但若轉換個切入點: 觀察“過定點的k個圓及k+1個圓,其最多分

割區域數的關係”,則問題較易掌握. 同理, 面對「流浪漢在城鎮間流浪」

的機率問題時,我們以“流浪漢於前後兩夜在各城鎮的機率有何關係?”為

切入點,則可避免繁複的樹形圖分析,尤其是問及第7夜,第8夜L流浪漢在

各城鎮的機率時,這種思路更顯示出其靈巧!

 

 

【習題】

1.平面上n條直線最多將平面分割成多少區域?

(1)設最多分割區域數an,試求a1=? a2=? a3=? a4=? 並猜測an與an+1的關係

(2)承(1),求得a­n=?

2.平面上n個圓最多將平面分割成多少區域?

(1)設最多分割區域數an,試求a1=? a2=? a3=? a4=? 並猜測an與an+1的關係

(2)承(1),求得a­n=?

3. 設A,D為一正六邊形相對的兩頂點, 一隻青蛙從A點開始跳動, 由正六邊

形的每一頂點都可以跳至與它相鄰兩頂點中的任何其一. 令an表經n次跳

動後到達D點的所有跳動路線數,試求an=?                       ·D

4.High-way star在公路沿途的五個城鎮A,B,C,D,E遊蕩.城鎮的相鄰   ·B

關係如右圖,每日清晨,此人決定當日夜晚留宿該鎮,或改而前往     ·A

相鄰任一鎮的機率相等. 若此人第一夜宿於A鎮, 設第n夜       ·C

亦宿於A鎮之機率為Pn, 則P3=    ,P4=    ,P5=    .           ·E