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

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

的函數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每一邊直線段       轉變成折線段      所構成

 

 

 

 

 

 

 

 

 

問題研究平面上過定點An個圓最多將平面分割成多少區域?

 

 

 

 

 

問題研究古印度梵天塔 (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,8L流浪漢在

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

 

 

習題

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

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

(2)(1),求得n=?

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

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

(2)(1),求得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