組合數(shù)學(xué)課件第六章遞推關(guān)系

組合數(shù)學(xué)課件第六章遞推關(guān)系第1頁(yè)，共63頁(yè)，2023年，2月20日，星期二目錄（1）第1章什么是組合數(shù)學(xué)1.1引例 1.2組合數(shù)學(xué)研究對(duì)象、內(nèi)容和方法第2章鴿巢原理2.1鴿巢原理：簡(jiǎn)單形式2.2鴿巢原理：加強(qiáng)形式2.3Ramsey定理2.4鴿巢原理與Ramsey定理的應(yīng)用本章小結(jié)習(xí)題第3章排列與組合3.1兩個(gè)基本的計(jì)數(shù)原理3.2集合的排列與組合3.3多重集的排列與組合本章小結(jié)習(xí)題第四章二項(xiàng)式系數(shù)4.1二項(xiàng)式定理4.2組合恒等式4.3非降路徑問(wèn)題4.4牛頓二項(xiàng)式定理4.5多項(xiàng)式定理4.6基本組合計(jì)數(shù)的應(yīng)用本章小結(jié)習(xí)題第五章包含排斥原理5.1包含排斥原理5.2多重集的r-組合數(shù)5.3錯(cuò)位排列5.4有限制條件的排列問(wèn)題5.5有禁區(qū)的排列問(wèn)題本章小結(jié)習(xí)題目錄第2頁(yè)，共63頁(yè)，2023年，2月20日，星期二目錄（2）

第六章遞推關(guān)系6.1Fibonacci數(shù)列6.2常系數(shù)線性齊次遞推關(guān)系的求解6.3常系數(shù)線性非齊次遞推關(guān)系的求解6.4用迭代和歸納法求解遞推關(guān)系本章小結(jié)習(xí)題第七章生成函數(shù)7.1生成函數(shù)的定義和性質(zhì)7.2多重集的r-組合數(shù)7.3正整數(shù)的劃分7.4指數(shù)生成函數(shù)與多重集的排列問(wèn)題7.5Catalan數(shù)和Stiring數(shù)本章小結(jié)習(xí)題

第八章Polya定理8.1置換群中的共軛類與軌道8.2Polya定理的特殊形式及其應(yīng)用本章小結(jié)習(xí)題**********************課程總結(jié)第3頁(yè)，共63頁(yè)，2023年，2月20日，星期二第6章遞推關(guān)系

本章主要介紹遞推關(guān)系的建立及幾種常見(jiàn)的求解方法：6.1Fibonacci數(shù)列6.2常系數(shù)線性齊次遞推關(guān)系的求解6.3常系數(shù)線性非齊次遞推關(guān)系的求解6.4用迭代和歸納法求解遞推關(guān)系第4頁(yè)，共63頁(yè)，2023年，2月20日，星期二第6章遞推關(guān)系教學(xué)目標(biāo)：1．掌握幾種遞推關(guān)系的建立方法；2．理解并掌握常系數(shù)線性齊次及非齊次遞推關(guān)系的求解方法；3．能運(yùn)用迭代歸納法求解遞推關(guān)系；4．記住并理解Fibonacci數(shù)的定義及遞推公式，會(huì)推導(dǎo)Fibonacci數(shù)的一些性質(zhì)，能運(yùn)用它們解決一些組合計(jì)數(shù)問(wèn)題。重點(diǎn)：遞推關(guān)系的建立方法、常系數(shù)線性齊次及非齊次遞推關(guān)系的求解方法、Fibonacci數(shù)和Catalan數(shù)的定義、遞推公式及性質(zhì)難點(diǎn)：Catalan數(shù)的定義、遞推公式及性質(zhì)第6章遞推關(guān)系第5頁(yè)，共63頁(yè)，2023年，2月20日，星期二§6.1遞推關(guān)系定義§6.1遞推關(guān)系的建立定義6.1設(shè){H(n)}為一序列，把該序列中H(n)和它前面幾個(gè)H(i)(0≤i≤n-1)用等號(hào)（或大于、小于號(hào)）關(guān)聯(lián)起來(lái)的方程稱做一個(gè)遞推關(guān)系（遞歸關(guān)系）。

如第3章的錯(cuò)排數(shù)Dn=(n-1)(Dn-1+Dn-2)，(n≥3)

和關(guān)系式an=3an-1，(n≥1)都是遞推關(guān)系。如a0=d0

,a1=d1,…,ak=dk，di為常數(shù)(i=0,1,…,k)，稱為遞推關(guān)系的初值。

如D1=0,D2=1作為初值即可惟一的確定序列(D0,D1,…,Dn,…)，a0=1作為初值即可惟一的確定序列(1,3,32,…,3n,…)。將遞推關(guān)系和初值結(jié)合起來(lái)稱為帶初值的遞推關(guān)系。如第6頁(yè)，共63頁(yè)，2023年，2月20日，星期二§6.1遞推關(guān)系建立例1-1§6.1遞推關(guān)系的建立（Fibonacci數(shù)列）例題例1、在一個(gè)平面上有一個(gè)圓和n條直線，這些直線中的每一條在圓內(nèi)都同其他的直線相交。如果沒(méi)有多于三條的直線相交于一點(diǎn)，試問(wèn)這些直線將圓分成多少個(gè)不同區(qū)域？第7頁(yè)，共63頁(yè)，2023年，2月20日，星期二§6.1遞推關(guān)系建立例1-2§6.1遞推關(guān)系的建立例題解：要求解這個(gè)問(wèn)題，首先必須建立遞推關(guān)系，然后求解遞推關(guān)系即可。設(shè)這n條直線將圓分成的區(qū)域數(shù)為an，如果有n-1條直線將圓分成an-1個(gè)區(qū)域，那么再加入第n條直線與在圓內(nèi)的其他n-1條直線相交。顯然，這條直線在圓內(nèi)被分成n條線段，而每條線段又將第n條直線在圓內(nèi)經(jīng)過(guò)的區(qū)域分成兩個(gè)區(qū)域。這樣，加入第n條直線后，圓內(nèi)就增加了n個(gè)區(qū)域。而對(duì)于n=0，顯然有a0=1，于是對(duì)于每個(gè)整數(shù)n，可以建立如下帶初值的遞推關(guān)系（求解方法以后幾節(jié)再介紹）這就是問(wèn)題的解答。第8頁(yè)，共63頁(yè)，2023年，2月20日，星期二§6.1遞推關(guān)系建立例2§6.1遞推關(guān)系的建立例題例2、在一個(gè)平面中，有n個(gè)圓兩兩相交，但任二個(gè)圓不相切，任三個(gè)圓無(wú)公共點(diǎn)，求這n個(gè)圓把平面分成多個(gè)區(qū)域？解：設(shè)這n個(gè)圓將平面分成an個(gè)區(qū)域。如圖。易見(jiàn)，a1=2,a2=4?，F(xiàn)在假設(shè)前n-1個(gè)圓將平面分成了an-1個(gè)區(qū)域，當(dāng)加入第n個(gè)圓時(shí)，由題設(shè)這個(gè)圓與前面的n-1個(gè)圓一定交于2(n-1)個(gè)點(diǎn)，這2(n-1)個(gè)點(diǎn)把第n個(gè)圓分成2(n-1)條弧，而每條弧正好將前面的n-1個(gè)圓分成的區(qū)域中的其經(jīng)過(guò)的每個(gè)區(qū)域分成2個(gè)區(qū)域，故新加入的第n個(gè)圓使所成的區(qū)域數(shù)增加了2(n-1)。因此可以建立如下帶初值的遞推關(guān)系：

求解這個(gè)遞推關(guān)系可以得到問(wèn)題的解答。第9頁(yè)，共63頁(yè)，2023年，2月20日，星期二§6.1遞推關(guān)系建立例3-1§6.1遞推關(guān)系的建立例題例3、“Fibonacci兔子問(wèn)題”也是組合數(shù)學(xué)中的著名問(wèn)題之一。這個(gè)問(wèn)題是指：從某一年某一月開(kāi)始，把雌雄各一的一對(duì)兔子放入養(yǎng)殖場(chǎng)中，從第二個(gè)月雌兔每月產(chǎn)雌雄各一的一對(duì)新兔。每對(duì)新兔也是從第二個(gè)月起每月產(chǎn)一對(duì)兔子。試問(wèn)第n個(gè)月后養(yǎng)殖場(chǎng)中共有多少對(duì)兔子？第10頁(yè)，共63頁(yè)，2023年，2月20日，星期二§6.1遞推關(guān)系建立例3-1

表示幼兔表示成兔實(shí)線表示成長(zhǎng)虛線表示生殖1:12:13:24:35:56:87:13§6.1遞推關(guān)系的建立第11頁(yè)，共63頁(yè)，2023年，2月20日，星期二§6.1遞推關(guān)系建立例3-2§6.1遞推關(guān)系的建立例題解：設(shè)第n個(gè)月時(shí)養(yǎng)殖場(chǎng)中兔子的對(duì)數(shù)為Fn。并定義F0=1，顯然有，F(xiàn)1=1。由于在第n個(gè)月時(shí)，除了有第n-1個(gè)月時(shí)養(yǎng)殖場(chǎng)中的全部兔子Fn-1外，還應(yīng)該有Fn-2對(duì)新兔子，這是因?yàn)樵诘趎-2個(gè)月就已經(jīng)有的每對(duì)兔子，在第n個(gè)月里都應(yīng)生一對(duì)新的兔子。因此可以建立如下帶初值的遞推關(guān)系

求解上式可以得到我們所需的答案。注：利用該式我們可以推得(F0,F1,…,Fn,…)=(1,1,2,3,5,8,13,21,34,55,…)常稱Fn為Fibonacci數(shù)，(F0,F1,…,Fn,…)為Fibonacci數(shù)列。Fibonacci數(shù)列在數(shù)學(xué)中是一個(gè)奇特而又常見(jiàn)的序列，它在算法分析中起著重要的作用。注：以上各例均為經(jīng)典組合數(shù)學(xué)問(wèn)題，在算法分析中常用；對(duì)普通的遞推關(guān)系無(wú)一般規(guī)則可解。

第12頁(yè)，共63頁(yè)，2023年，2月20日，星期二§6.1Fibonacci數(shù)列應(yīng)用及性質(zhì)§6.1遞推關(guān)系的建立Fibonacci數(shù)列在組合計(jì)數(shù)中的應(yīng)用例：確定2×n棋盤用多米諾牌完美覆蓋的方法數(shù)hn。規(guī)定h0=1.容易看到h1=1，h2=2，h3=3。

hn=hn1

滿足斐波那契遞推關(guān)系。hn是斐波那契數(shù)。

+hn2第13頁(yè)，共63頁(yè)，2023年，2月20日，星期二

再如，一個(gè)人站在“梯子格”的起點(diǎn)處向上跳，從格外只能進(jìn)入第1格，從格中，每次可向上跳一格或兩格，問(wèn)：可以用多少種方法，跳到第n格？§6.1遞推關(guān)系的建立Fibonacci數(shù)列在組合計(jì)數(shù)中的應(yīng)用解：設(shè)跳到第n格的方法有種。由于他跳入第1格，只有一種方法；跳入第2格，必須先跳入第1格，所以也只有一種方法，從而第14頁(yè)，共63頁(yè)，2023年，2月20日，星期二

而能一次跳入第n格的，只有第和第兩格，因此，跳入第格的方法數(shù)，是跳入第格的方法數(shù)，加上跳入第格的方法數(shù)之和。即。綜合得遞推公式

容易算出，跳格數(shù)列就是斐波那契數(shù)列

1，1，2，3，5，8，13，21，34，…§6.1遞推關(guān)系的建立Fibonacci數(shù)列在組合計(jì)數(shù)中的應(yīng)用第15頁(yè)，共63頁(yè)，2023年，2月20日，星期二§6.1Fibonacci數(shù)列應(yīng)用及性質(zhì)§6.1遞推關(guān)系的建立類似的例子奇妙的斐波那契序列斐波那契螺旋線數(shù)第16頁(yè)，共63頁(yè)，2023年，2月20日，星期二6.1Fibonacci數(shù)列應(yīng)用及性質(zhì)樹(shù)杈的數(shù)目13853211§6.1遞推關(guān)系的建立類似的例子第17頁(yè)，共63頁(yè)，2023年，2月20日，星期二§6.1Fibonacci數(shù)列應(yīng)用及性質(zhì)（1）§6.1遞推關(guān)系的建立Fibonacci數(shù)列性質(zhì)1.Fibonacci數(shù)可以表示為二項(xiàng)式系數(shù)之和，即證明當(dāng)時(shí)，有，即，所以只要證明下面的等式成立，即證用歸納法。當(dāng)時(shí)，有成立。假設(shè)對(duì)等式都成立，則有第18頁(yè)，共63頁(yè)，2023年，2月20日，星期二§6.1Fibonacci數(shù)列應(yīng)用及性質(zhì)由歸納法，命題成立?！?.1遞推關(guān)系的建立Fibonacci數(shù)列性質(zhì)第19頁(yè)，共63頁(yè)，2023年，2月20日，星期二§6.1Fibonacci數(shù)列應(yīng)用及性質(zhì)（2）§6.1遞推關(guān)系的建立Fibonacci數(shù)列性質(zhì)2.Fibonacci數(shù)證明把以上各式的左邊和右邊分別相加，得第20頁(yè)，共63頁(yè)，2023年，2月20日，星期二§6.1Fibonacci數(shù)列應(yīng)用及性質(zhì)（3-4）§6.1遞推關(guān)系的建立Fibonacci數(shù)列性質(zhì)3.Fibonacci數(shù)證明把以上各式的左邊和右邊分別相加，得4.Fibonacci數(shù)證明由性質(zhì)2和3即得.第21頁(yè)，共63頁(yè)，2023年，2月20日，星期二§6.1Fibonacci數(shù)列應(yīng)用及性質(zhì)（5）§6.1遞推關(guān)系的建立Fibonacci數(shù)列性質(zhì)5.證明把以上各式的左邊和右邊分別相加，得第22頁(yè)，共63頁(yè)，2023年，2月20日，星期二§6.1Fibonacci數(shù)列應(yīng)用及性質(zhì)（6）§6.1遞推關(guān)系的建立Fibonacci數(shù)列性質(zhì)6.證明由歸納法，等式成立。對(duì)進(jìn)行歸納.當(dāng)時(shí)，有成立，假設(shè)對(duì)一切有等式成立，則第23頁(yè)，共63頁(yè)，2023年，2月20日，星期二§6.1Fibonacci數(shù)列應(yīng)用及性質(zhì)§6.1遞推關(guān)系的建立Fibonacci數(shù)列性質(zhì)

關(guān)于Fibonacci數(shù)列的性質(zhì)還有許多，習(xí)題上也列出了一部分，這里就不一一介紹。利用這些性質(zhì)，我們可以將比較大的n的Fibonacci數(shù)化成較小的的Fibonacci數(shù)，從而使計(jì)算更為方便。第24頁(yè)，共63頁(yè)，2023年，2月20日，星期二§6.2常系數(shù)線遞推關(guān)系次遞推關(guān)系§6.2常系數(shù)線性齊次遞推關(guān)系定義6.2

若{H(n)}中相鄰k+1項(xiàng)滿足H(n)=a1H(n-1)+a2H(n-2)+…+akH(n-k)，(n≥k)稱之為{H(n)}的k階常系數(shù)線性齊次遞推關(guān)系。其中ai(i=1,2,…,k)是常數(shù)，且ak≠0。該遞推關(guān)系還可以寫作

H(n)-a1H(n-1)-a2H(n-2)-…-akH(n-k)=0.H(0)=d0,

H(1)=d1,

…,

H(k-1)=dk-1稱為初始條件，其中di(i=0,2,…,k-1)是常數(shù)；定義6.3C(x)=xk-a1xk-1-a2xk-2-…-ak稱為上述遞推關(guān)系的特征多項(xiàng)式；

C(x)=0稱為上述遞推關(guān)系的特征方程；該方程的k個(gè)根q1,q2,…qk稱為上述遞推關(guān)系的特征根.其中qi(i=1,2,…,k)是復(fù)數(shù).第25頁(yè)，共63頁(yè)，2023年，2月20日，星期二§6.2常系數(shù)線遞推關(guān)系次遞推關(guān)系定理6.1對(duì)此，有下面的定理定理6.1§6.2常系數(shù)線性齊次遞推關(guān)系設(shè)k階常系數(shù)線性齊次遞推關(guān)系{H(n)}為若q≠0,H(n)=qn是上述遞推關(guān)系的解，當(dāng)且僅當(dāng)q是上述特征方程的解。證明：若q0,H(n)=qn是遞推關(guān)系的解

qn

=a1qn-1

+a2qn-2

+…+akqn-k(n≥k)qk

=a1qk-1

+a2qk-2

+…+ak

q是特征方程xk-a1xk-1-a2xk-2-…-ak=0的根。證畢。第26頁(yè)，共63頁(yè)，2023年，2月20日，星期二定理6.2

若都是齊次遞推關(guān)系的解，那么也是齊次遞推關(guān)系的解。證:由是齊次遞推關(guān)系的解知§6.2常系數(shù)線遞推關(guān)系次遞推關(guān)系定理6.2§6.2常系數(shù)線性齊次遞推關(guān)系第27頁(yè)，共63頁(yè)，2023年，2月20日，星期二§6.2常系數(shù)線性齊次相異特征根定理6.3§6.2常系數(shù)線性齊次遞推關(guān)系6.2.1相異特征根的解法定理6.3若q1,q2,…,qk,為上述遞推關(guān)系的特征根（相異），c1,

c2,…,ck為任意常數(shù)，則an=c1q1n+c2q2n+…+ckqkn為上述遞推關(guān)系的解。證明：由于qi(i=1,2,…,k)是特征方程xk-b1xk-1-b2xk-2-…-bk=0的根，由定理6.1有qin

=b1qin-1

+b2qin-2

+…+bk

qin-k，i=1,2,…,k將上式兩邊同乘以ci

，然后從1到k求和有因此an=c1q1n+c2q2n+…+ckqkn是遞推關(guān)系an=b1an-1+b2an-2+…+bkan-k的解。第28頁(yè)，共63頁(yè)，2023年，2月20日，星期二§6.2常系數(shù)線性齊次相異特征根定義6.4§6.2常系數(shù)線性齊次遞推關(guān)系6.2.1相異特征根的解法定義6.4如果對(duì)于遞推關(guān)系H(n)=b1H(n-1)+b2H(n-2)+…+bkH(n-k)的每個(gè)解h(n)都可以選擇一組常數(shù)使得成立，則稱是遞推關(guān)系的通解，其中為任意常數(shù)。第29頁(yè)，共63頁(yè)，2023年，2月20日，星期二§6.2常系數(shù)線性齊次相異特征根定理6.4§6.2常系數(shù)線性齊次遞推關(guān)系6.2.1相異特征根的解法定理6.4若q1,q2,…,qk為上述遞推關(guān)系的特征根（相異），則an=c1q1n+c2q2n+…+ckqkn為上述遞推關(guān)系的通解，其中ci由初始條件確定。證明：由定理6.2知，an=c1q1n+c2q2n+…+ckqkn是遞推關(guān)系an=b1an-1+b2an-2+…+bkan-k的解。只需證明，若該式滿足遞推關(guān)系式an=b1an-1+b2an-2+…+bkan-k的任意初值條件式a0=d0,a1=d1,

…,

ak-1=dk-1所得到的關(guān)于c1,c2,…,ck的線性方程組有惟一解即可。由初值條件式a0=d0,a1=d1,…,ak-1=dk-1，我們得到因此，上述線性方程組關(guān)于c1,c2,…,ck有惟一的解。從而證明了an=c1q1n+c2q2n+…+ckqkn

是遞推關(guān)系的an=b1an-1+b2an-2+…+bkan-k的通解。第30頁(yè)，共63頁(yè)，2023年，2月20日，星期二例1、求遞歸關(guān)系§6.2常系數(shù)線性齊次例1§6.2常系數(shù)線性齊次遞推關(guān)系5.2.1相異特征根的解法例題第31頁(yè)，共63頁(yè)，2023年，2月20日，星期二§6.2常系數(shù)線性齊次例2§6.2常系數(shù)線性齊次遞推關(guān)系6.2.1相異特征根的解法例題例2、求遞歸關(guān)系

第32頁(yè)，共63頁(yè)，2023年，2月20日，星期二§6.2常系數(shù)線性齊次例3-1§6.2常系數(shù)線性齊次遞推關(guān)系6.2.1相異特征根的解法例題例3、用字母a,b和c組成長(zhǎng)度是n的字，如果要求沒(méi)有兩個(gè)a相鄰，問(wèn)這樣的字有多少個(gè)？解設(shè)h(n)是所求的字的個(gè)數(shù)，n≥1.易見(jiàn)，長(zhǎng)為1的且沒(méi)有兩個(gè)a相鄰的字有a,b和c，所以h(1)=3.長(zhǎng)為2的沒(méi)有兩個(gè)a相鄰的字有ab,ac,ba,bb,bc,ca,cb,cc.所以h(2)=8.

設(shè)n≥

3,如果字中的第一個(gè)字母是a，那么第二個(gè)字母只能是b或c,其余的字母可以有h(n-2)種方式來(lái)選擇，因此以a開(kāi)頭的字有2h(n-2)個(gè).如果字中的第一個(gè)字母是b,那么這樣的字有h(n-1)個(gè)，同理以c開(kāi)頭的字也有h(n-1)個(gè)，由加法法則得第33頁(yè)，共63頁(yè)，2023年，2月20日，星期二§6.2常系數(shù)線性齊次例3-2§6.2常系數(shù)線性齊次遞推關(guān)系6.2.1相異特征根的解法例題例3、用字母a,b和c組成長(zhǎng)度是n的字，如果要求沒(méi)有兩個(gè)a相鄰，問(wèn)這樣的字有多少個(gè)？第34頁(yè)，共63頁(yè)，2023年，2月20日，星期二§6.2常系數(shù)線性齊次相同特征根定理6.5§6.2常系數(shù)線性齊次遞推關(guān)系6.2.2相同特征根的解法定理6.5若q為上述遞推關(guān)系的特征方程C(x)=0的一個(gè)m重特征根，則qn,nqn,…,nm-1qn為該遞推關(guān)系的解。證明：令P(x)=xk-b1xk-1-b2xk-2-…-bk，

Pn(x)=xn-kP(x)

=xn-b1xn-1-b2xn-2-…-bkxn-k。由于q是P(x)=0的m重根，故q也是Pn(x)=0的m重根，由高等代數(shù)的知識(shí)知，q也是P'n(x)=0的(m-1)重根，那么q也是xP'n(x)=0的(m-1)重根，即q是方程nxn-b1(n-1)xn-1-b2(n-2)

xn-2-…-bk(n-k)xn-k=0的(m-1)重根。類似地，q是方程n2xn-b1(n-1)2xn-1-b2(n-2)2xn-2-…-bk(n-k)2xn-k=0的(m-2)重根?！话愕?，對(duì)任意的i,i＜m,q是方程nixn-b1(n-1)ixn-1-b2(n-2)ixn-2-…-bk(n-k)i

xn-k=0的(m-i)重根。即有niqn-b1(n-1)iqn-1-b2(n-2)iqn-2-…-bk(n-k)iqn-k=0。分別令i=1,2,…,m-1，知nqn,n2qn,…,nm-1qn都是遞推關(guān)系an=b1an-1+b2an-2+…+bkan-k的解，而qn是遞推關(guān)系an=b1an-1+b2an-2+…+bkan-k的解在定理6.1中已經(jīng)證明。故定理得證。第35頁(yè)，共63頁(yè)，2023年，2月20日，星期二§6.2常系數(shù)線性齊次相同特征根定理6.6-1§6.2常系數(shù)線性齊次遞推關(guān)系6.2.2相同特征根的解法定理6.6若q1,q2,…,qt分別為上述遞推關(guān)系的特征方程C(x)=0相異的m1,m2,…,mt重特征根，

為該遞推關(guān)系的通解，其中cij由初始條件確定。第36頁(yè)，共63頁(yè)，2023年，2月20日，星期二§6.2常系數(shù)線性齊次相同特征根定理6.6-2§6.2常系數(shù)線性齊次遞推關(guān)系5.2.2相同特征根的解法證明：由定理6.4知，表達(dá)式的右端每一項(xiàng)都是遞推關(guān)系an=b1an-1+b2an-2+…+bkan-k的解。故an也是該遞推關(guān)系的解。現(xiàn)只需證明該式滿足遞推關(guān)系式an=b1an-1+b2an-2+…+bkan-k的任意初值條件式a0=d0,a1=d1,…,

ak-1=dk-1所得的線性方程組有惟一解即可。將初值條件式a0=d0,a1=d1,…,ak-1=dk-1代入式(A)得到下列方程組：這個(gè)方程組的系數(shù)行列式是Vandermonde行列式的一個(gè)推廣。其行列式之值為故方程組有惟一解。即cij(i=1,2,…,t;j=1,2,…,mi)是由初值惟一確定，定理得證。第37頁(yè)，共63頁(yè)，2023年，2月20日，星期二例4、求遞歸關(guān)系

§6.2常系數(shù)線性齊次例4§6.2常系數(shù)線性齊次遞推關(guān)系6.2.2相同特征根的解法例題第38頁(yè)，共63頁(yè)，2023年，2月20日，星期二例5、求遞歸關(guān)系

§6.2常系數(shù)線性齊次例5§6.2常系數(shù)線性齊次遞推關(guān)系6.2.2相同特征根的解法例題第39頁(yè)，共63頁(yè)，2023年，2月20日，星期二§6.2常系數(shù)線性齊次例6§6.2常系數(shù)線性齊次遞推關(guān)系6.2.2相同特征根的解法例題例6、求遞歸關(guān)系第40頁(yè)，共63頁(yè)，2023年，2月20日，星期二§6.2常系數(shù)線性齊次例7§6.2常系數(shù)線性齊次遞推關(guān)系5.2.2相同特征根的解法例題例7、計(jì)算n階行列式的值：解：設(shè)具有以上形式的n階行列式的值為an，按第一列展開(kāi)有

顯然a1=2，a2=3，于是可建立遞推關(guān)系如下這個(gè)遞推關(guān)系就是例3所求解的遞推關(guān)系，故由例3的結(jié)果可知第41頁(yè)，共63頁(yè)，2023年，2月20日，星期二§6.2常系數(shù)線性齊次注意事項(xiàng)§6.2常系數(shù)線性齊次遞推關(guān)系6.2.2相同特征根的解法注意：

建立遞推關(guān)系關(guān)系時(shí)可考慮某個(gè)特定數(shù)值，如第一個(gè)、最后一個(gè)等；

k次遞推關(guān)系需要k個(gè)初值，一般從a0開(kāi)始（不妨假設(shè)）；結(jié)果需要驗(yàn)證（n=k+1,k+2,…）。

第42頁(yè)，共63頁(yè)，2023年，2月20日，星期二§6.3常系數(shù)線性非齊次定義§6.3常系數(shù)線性非齊次遞推關(guān)系定義6.4

若{H(n)}中相鄰k+1項(xiàng)滿足:H(n)=b1H(n-1)+b2H(n-2)+…+bkH(n-k)+f(n)，(n≥k)稱之為{H(n)}的k階常系數(shù)線性非齊次遞推關(guān)系。其中bi(i=1,2,…,k)是常數(shù)，且bk≠0，f(n)≠0

。

若f(n)=0，稱

=b1H(n-1)+b2H(n-2)+…+bkH(n-k)為上述遞推關(guān)系導(dǎo)出的常系數(shù)線性齊次遞推關(guān)系。第43頁(yè)，共63頁(yè)，2023年，2月20日，星期二§6.3常系數(shù)線性非齊次定理6.7-1§6.3常系數(shù)線性非齊次遞推關(guān)系定理6.7若

為an=b1an-1+b2an-2+…+bkan-k+f(n)

的一個(gè)特解，

為=b1an-1+b2an-2+…+bkan-k的一個(gè)通解，則an=

+

為原非齊次遞推關(guān)系的通解。證明：由于

是非齊次遞推關(guān)系式導(dǎo)出的齊次線性遞推關(guān)系式即 的通解，故有又由于是非齊次遞推關(guān)系的一個(gè)特解，故有將以上兩式的兩邊分別相加得由上式可見(jiàn)

是式 的解。設(shè)非線性齊次遞推關(guān)系為：an=b1an-1+b2an-2+…+bkan-k+f(n)第44頁(yè)，共63頁(yè)，2023年，2月20日，星期二§6.3常系數(shù)線性非齊次定理6.7-2§6.3常系數(shù)線性非齊次遞推關(guān)系定理6.7若

為an=b1an-1+b2an-2+…+bkan-k+f(n)

的一個(gè)特解，

為=b1an-1+b2an-2+…+bkan-k的一個(gè)通解，則an=

+

為原非齊次遞推關(guān)系的通解?，F(xiàn)只需證明

能滿足式 的任意初值條件式所導(dǎo)出的關(guān)于c1,c2,…,ck為未知數(shù)的線性方程組有惟一解即可。式中 。而這是顯然的。因?yàn)樵摲匠探M的系數(shù)矩陣是一個(gè)Verdermonde矩陣，其行列式的值不為0。故定理得證。第45頁(yè)，共63頁(yè)，2023年，2月20日，星期二§6.3常系數(shù)線性非齊次定理6.7-3§6.3常系數(shù)線性非齊次遞推關(guān)系定理6.7若

為an=b1an-1+b2an-2+…+bkan-k+f(n)

的一個(gè)特解，

為=b1an-1+b2an-2+…+bkan-k的一個(gè)通解，則an=

+

為原非齊次遞推關(guān)系的通解。

注：定理6.7指出，若要求一個(gè)常系數(shù)線性非齊次遞推關(guān)系式的通解，必須先求出這個(gè)遞推關(guān)系所導(dǎo)出的常系數(shù)線性齊次遞推關(guān)系的通解，然后再求這個(gè)遞推關(guān)系式的一個(gè)特解，將其相加即可。然而，求一個(gè)非齊次線性遞推關(guān)系的特解，通常沒(méi)有系統(tǒng)的方法，但當(dāng)函數(shù)f(n)是某些特殊形式時(shí)，才有一些規(guī)范的求法。第46頁(yè)，共63頁(yè)，2023年，2月20日，星期二

若f(n)為n的k次多項(xiàng)式，則

=A0nk+A1nk-1+…+Ak，其中A0,

A1,…,Ak為待定系數(shù)；若導(dǎo)出的常系數(shù)線性齊次遞推關(guān)系特征根為1的m重根，則

=(A0nk+A1nk-1+…+Ak)nm?！?.3常系數(shù)線性非齊次特殊形式§6.3常系數(shù)線性非齊次遞推關(guān)系

可針對(duì)f(n)的某些特定形式，轉(zhuǎn)化為齊次性。

若f(n)為βn的形式，如β不是導(dǎo)出的常系數(shù)線性齊次遞推關(guān)系特征根，則

=Aβn，其中A為待定系數(shù)；若β是導(dǎo)出的常系數(shù)線性齊次遞推關(guān)系的k重特征根根，則

=(A0nk+A1nk-1+…+Ak)βn。第47頁(yè)，共63頁(yè)，2023年，2月20日，星期二§6.3常系數(shù)線性非齊次例1§6.3常系數(shù)線性非齊次遞推關(guān)系例題例1、求遞歸關(guān)系

第48頁(yè)，共63頁(yè)，2023年，2月20日，星期二§6.3常系數(shù)線性非齊次例2-1§6.3常系數(shù)線性非齊次遞推關(guān)系例題例2、“Hanoi塔”問(wèn)題：n個(gè)大小不一的圓盤依半徑的大小，從下而上的套在柱子A上。如圖所示。現(xiàn)要求將所有的圓盤從柱子A上全部移到柱子C上，每次只允許從一根柱子上轉(zhuǎn)移一個(gè)圓盤到另一根柱子上，且在轉(zhuǎn)移過(guò)程中不允許出現(xiàn)大圓盤放到小圓盤上。試問(wèn)至少要轉(zhuǎn)移多少次才能將柱子上的n個(gè)圓盤全部轉(zhuǎn)移到柱子C上去？第49頁(yè)，共63頁(yè)，2023年，2月20日，星期二§6.3常系數(shù)線性非齊次例2-2§6.3常系數(shù)線性非齊次遞推關(guān)系例題解：用an表示從一根柱子上的n個(gè)圓盤全部轉(zhuǎn)移到另一根柱子上的轉(zhuǎn)移次數(shù)。顯然，a1=1,a2=3。當(dāng)n≥3時(shí)，要將柱子A上的n個(gè)圓盤轉(zhuǎn)移到柱子C上，可以這樣設(shè)想。先把柱子A上的n-1個(gè)圓盤轉(zhuǎn)移到柱子B上，這需要轉(zhuǎn)移an-1次；然后把柱子A上最后一個(gè)圓盤轉(zhuǎn)移到柱子C上，顯然這需要轉(zhuǎn)移一次；最后再把柱子B上的n-1個(gè)圓盤轉(zhuǎn)移到柱子C上，這也需要轉(zhuǎn)移an-1次。經(jīng)過(guò)這些步驟后，所有A上的n個(gè)圓盤就全部轉(zhuǎn)移到柱子C上。由加法法則，這一共轉(zhuǎn)移了2an-1+1次。于是可以建立如下帶初值的遞推關(guān)系

這就是我們需要的結(jié)果。第50頁(yè)，共63頁(yè)，2023年，2月20日，星期二§6.3常系數(shù)線性非齊次例2-3§6.3常系數(shù)線性非齊次遞推關(guān)系例題例2、求遞歸關(guān)系（Hanoi塔）

第51頁(yè)，共63頁(yè)，2023年，2月20日，星期二§6.3常系數(shù)線性非齊次例3§6.3常系數(shù)線性非齊次遞推關(guān)系例題例3、求遞歸關(guān)系

第52頁(yè)，共63頁(yè)，2023年，2月20日，星期二§6.3常系數(shù)線性非齊次例4§6.3常系數(shù)線性非齊次遞推關(guān)系例題例4、求遞歸關(guān)系

an+2an-1+an-2=2n的通解。第53頁(yè)，共63頁(yè)，2023年，2月20日，星期二§6.3常系數(shù)線性非齊次例5§6.3常系數(shù)線性非齊次遞推關(guān)系例題例5、求遞歸關(guān)系

an-4an-1+4an-2=2n的通解。第54頁(yè)，共63頁(yè)，2023年，2月20日，星期二§6.3常系數(shù)線性非齊次例6§6.3常系數(shù)線性非齊次遞推關(guān)系例題例6、求Sn=1+2+3+…+n。第55頁(yè)，共63頁(yè)，2023年，2月20日，星期二§6.3常系數(shù)線性非齊次例7§6.3常系數(shù)線性非齊次遞推關(guān)系例題例7、求Sn=12+22+32+…+n2。第56頁(yè)，共63頁(yè)，2023年，2月20日，星期二§6.3常系數(shù)線性非齊次例8§6.3常系數(shù)線性非齊次遞推關(guān)系