遞推關(guān)系和生成函數(shù)

1、第七章 遞推關(guān)系和生成函數(shù)7.1 某些數(shù)列（1）等差數(shù)列（算術(shù)數(shù)列）h0, h0+q, h0+2q, , h0+nq,遞推關(guān)系：hn= hn-1+q一般項(xiàng)： hn= h0+nq前n+1項(xiàng)和：sn= (n+1)h0+q(n)(n+1)/2（2）等比數(shù)列（幾何數(shù)列）h0, qh0, q2h0, , qnh0,遞推關(guān)系：hn= qhn-1一般項(xiàng)： hn= qnh0前n+1項(xiàng)和：sn= h0(1-qn+1)/(1-q) 例1：確定平面一般位置上的n個互相交疊的圓所形成的區(qū)域數(shù)。（互相交疊是指每兩個圓相交在不同的兩個點(diǎn)上；一般位置是指沒有同心圓）例2：年初把性別相反的一對新生兔子放進(jìn)圍欄，從第二個月開始

2、每月生出一對性別相反的兔子，每對新兔也從第二個月開始每月生出一對性別相反的兔子，問一年后圍欄內(nèi)共有多少對兔子。定義1：設(shè)f0=0, f1=1, 那么滿足遞推關(guān)系fn= fn-1+ fn-2, 的序列叫斐波那契（Fibonacci）序列。結(jié)論：Fibonacci序列的部分和為sn= f0+ f1+ fn= fn+2-1.定理7.1.1：Fibonacci序列的一般項(xiàng)公式為：fn=（）n -（）n定理7.1.2沿Pascal三角形左邊向上對角線上的二項(xiàng)式系數(shù)和是Fibonacci數(shù),即fn=+, 其中:k=ëû.7.2 線性齊次遞推關(guān)系定義1:令h0, h1, h2, hn,是

3、一個數(shù)列,若存在量a1, a2, ,ak和bn(ak0,每個量是常數(shù)或依賴于n的數(shù))使得:hn= a1hn-1+ a2hn-2+ akhn-k+bn (nk)則稱序列滿足k階線性遞推關(guān)系. 若bn=0,稱齊次的;若a1, a2, ,ak取常數(shù),稱常系數(shù)的.定理7.2.1令q為一個非零數(shù),則hn=qn是常系數(shù)線性齊次遞推關(guān)系hn= a1hn-1+ a2hn-2+ akhn-k (ak0,nk) (1)的解,當(dāng)且僅當(dāng)q是多項(xiàng)式方程xk-a1xk-1- a2xk-2- ak=0(2)的一個根.若多項(xiàng)式方程有k個不同的根q1, q2, qk,則hn=c1q1n+ c2q2n+ ckqkn(3)是下述意

4、義下(1)的一般解: 無論給定h0, h1, ,hk-1什么初始值,都存在c1, c2, ck使得(3)式是滿足(1)式和初始條件的唯一的序列.例1:求滿足初始值h0=1, h1=2和h2=0的遞推關(guān)系:hn= 2hn-1+ hn-2- 2hn-3定理7.2.2令q1, q2, qt為常系數(shù)線性齊次遞推關(guān)系:hn= a1hn-1+ a2hn-2+ akhn-k (nk)的特征方程的互異的根,此時,如果qi是si的重根,則該遞推關(guān)系對qi的部分一般解為:Hn(i) = c1qin+ c2nqin+ csinsi-1qin遞推關(guān)系的一般解為:hn= Hn(1) + Hn(2) + Hn(t) 例2

5、:求解遞推關(guān)系hn= -hn-1+ 3hn-2+ 5hn-3+ 2hn-4 (n4)滿足初始條件h0=1, h1=0, h2=1和h3=2的解.7.3 非齊次遞推關(guān)系一般方法總結(jié):(1) 求齊次關(guān)系的一般解(2) 求非齊次關(guān)系的一個特解(3) 將一般解和特解結(jié)合,通過初始條件確定一般解中出現(xiàn)的常系數(shù)值.根據(jù)非齊次項(xiàng)bn 來嘗試某些類型的特解:(1) 若bn =d(常數(shù)), 嘗試hn =r(常數(shù));(2) 若bn =dn+c(d,c是常數(shù)), 嘗試hn =rn+s(r,s是常數(shù));(3) 若bn =fn2+dn+c(f,d,c是常數(shù)), 嘗試hn =rn+sn+t(r,s,t是常數(shù));(4) 若

6、bn =dn(d是常數(shù)), 嘗試hn =pdn(p是常數(shù));例1:解hn= 3hn-1- 4n (n1), 初始值h0=2.例2:解hn= 3hn-1+ 3n (n1), 初始值h0=2.7.4 生成函數(shù)定義1:令序列h0, h1, hn為一無窮序列,其生成函數(shù)定義為:g(x)= h0+ h1x+ h2x2+ hnxn+例1:設(shè)m是正整數(shù),求序列,的生成函數(shù).例2:設(shè)是實(shí)數(shù),求序列,的生成函數(shù).例3:設(shè)k是正整數(shù),求序列h0, h1, hn的生成函數(shù),其中一般項(xiàng)hn等于方程e1 + e1+ +ek =n的非負(fù)整數(shù)解個數(shù).解: hn相當(dāng)于具有無限重復(fù)次數(shù)的k 個不同元素的n組合個數(shù), hn=,其

7、生成函數(shù)g(x)=xn=反向思考該問題:若已知生成函數(shù)g(x)=,那么=.=(1+x+x2+) (1+x+x2+) (1+x+x2+)=. 其展開項(xiàng)xn= xe1. xe2. .xek = xe1+e2+.ek, 它的系數(shù)hn相當(dāng)于方程e1 + e1+ +ek =n的非負(fù)整數(shù)解個數(shù), hn=, 相當(dāng)于根據(jù)生成函數(shù)求解出具有無限重復(fù)次數(shù)的k 個不同元素的n組合個數(shù)hn. 若e1 , e1,ek 有不同的約束, 表現(xiàn)為不同的生成函數(shù), 若我們能求出該生成函數(shù)對應(yīng)的序列一般項(xiàng)hn.那么就相當(dāng)于在某種約束下求解出k 個不同元素的n組合個數(shù)hn.例4:確定蘋果,香蕉,橘子和梨的n組合個數(shù),其中每個n組合

8、中,蘋果的個數(shù)是偶數(shù),香蕉的個數(shù)是奇數(shù),橘子的個數(shù)在04之間,而且至少有一個梨.例5:確定蘋果,香蕉,橘子和梨的袋裝水果的袋數(shù)hn(即n組合數(shù)),其中每袋中蘋果的個數(shù)是偶數(shù),香蕉的個數(shù)是5的倍數(shù),橘子的個數(shù)最多4個,梨子的個數(shù)是0或1.7.5 遞歸和生成函數(shù)利用生成函數(shù)求解n階常系數(shù)線性齊次遞推關(guān)系:例1:求解初始值h0=1和h1=-2的遞推關(guān)系hn= 5hn-1-6hn-2 (n2)定理7.5.1令h0, h1, h2, hn,為滿足k階常系數(shù)線性齊次遞推關(guān)系:hn= c1hn-1+ c2hn-2+ ckhn-k (ck0,nk)(1)的數(shù)列,則它的生成函數(shù)g(x)形如:g(x)=(2)其中

9、:q(x)是具有非零常數(shù)次的k 次多項(xiàng)式,p(x)是小于k 次的多項(xiàng)式.反之, 給定這樣的多項(xiàng)式p(x)和q(x), 則存在序列h0, h1, h2, hn,滿足(1)式的k階常系數(shù)線性齊次遞推關(guān)系, 其生成函數(shù)由(2)式給出.關(guān)于解方程的已知結(jié)論:(1)對于4次以及4次以下的方程,目前已有代數(shù)解法.(在復(fù)數(shù)域內(nèi)求解)(2)阿貝爾定理:5次以及更高次的代數(shù)方程沒有一般的代數(shù)解法.7.6 一個幾何的例子定義1:設(shè)有平面或空間中的點(diǎn)集k, 若k中任意兩點(diǎn)p和q的連線pq上的所有點(diǎn)都在k內(nèi),稱k是凸的.定理7.6.1通過畫出在區(qū)域內(nèi)不相交的對角線,令hn表示具有n+1條邊的凸多邊形區(qū)域分成三角形區(qū)域的方法數(shù),定義h1=1,則hn滿足如下遞推關(guān)系:hn=h1hn-1+ h2hn-2+ h1hn-1+ hn-1h1= (n2)該遞推關(guān)系的解為:hn=7.7 指數(shù)生成函數(shù)定義1:設(shè)序列h0, h1, h2, hn, 定義其指數(shù)生成函數(shù)為:g(e)(x)= h0+ h1+ h2+ hn定理7.7.1令S=n1.a1, n2.a2, nk.ak 為一多重集,其中: n1, n2, nk 均為非負(fù)整數(shù),令hn表示S的