第三章 遞推關(guān)系§3.1§3.1基本觀點(diǎn)（一）遞推關(guān)系【定義】（隱式）對數(shù)列ai{迂b和隨意自然數(shù)n,一個(gè)關(guān)系到an和某些個(gè)aii<n的方程式，稱為遞推關(guān)系，記作Fa0,a,an=0an2-an2i-an2-2---a02-n2=02a3a 2a0—nn1 n_2【定義3.1.1】（顯式）對數(shù)列aii-0，把a(bǔ)n與其之前若干項(xiàng)聯(lián)系起來的等式對所有n三k均成立（k為某個(gè)給定的自然數(shù)），稱該等式為a：的遞推關(guān)系，記為()二_,a,,a_anFan1n2nk()例 an=3an」2an2工工2a1-1(二)分類(1)按常量部分:①齊次遞推關(guān)系：指常量=0,如F=F_F_；n n1 n2②非齊次遞推關(guān)系，即常量W0，如hn-2hn1=1。(2)按ai的運(yùn)算關(guān)系：①線性關(guān)系，F(xiàn)是對于ai的線性函數(shù)，如(1)中的Fn與hn均是這樣；②非線性關(guān)系，F(xiàn)是ai的非線性函數(shù)，如=hh_hh_…h(huán)n_1h1。n 1n1 2n2(3)按ai的系數(shù)：①常系數(shù)遞推關(guān)系，如(1)中的Fn與hn；②變系數(shù)遞推關(guān)系，如Pnnpn1_，PnL以前的系數(shù)是跟著n而變的。(4)按數(shù)列的多少:①一元遞推關(guān)系，此中的方程只波及一個(gè)數(shù)列，如()和(),均為一元的；②多元遞推關(guān)系，方程中波及多個(gè)數(shù)列，如q— —[an=7an_jbn」bn7bn1 an1(5)顯式與隱式：xn1y+= +xn1n1ynh-yn1word（三）定解【定】（定解）稱含有初始條件的推關(guān)系定解，其一般形式Fao,ai,,an0,. … _ （）a0do,a1 di,,ak1dk1解推關(guān)系，指依據(jù)式（）或。求an的與ao、ai、…、@口i沒關(guān)的分析表達(dá)式或數(shù)列｛an｝的母函數(shù)。（四）例【例】（Hanoi塔）n個(gè)按從小到大的序一次套在柱A上。定每次只好從一根柱子上搬一個(gè)到另一根柱子上，且要求在搬程中不允大放在小上，并且只有A、B、C三根柱子可供使用。用an表示將n個(gè)從柱A移到柱C上所需搬的最少次數(shù)，成立數(shù)列｛an｝的推關(guān)系。A IB C（解）特例:a1=1,a2=3,于任何n>3。一般情況：：第一步，將套在柱A的上部的n-1個(gè)按要求移到柱B上，共搬了an1次；第二步，將柱A上的最大一個(gè)盤移到柱C上，只需挪動(dòng)一次;次;第三步，再從柱B將n—1個(gè)盤按要求移到柱C上，也要用ani次。由加法法例:IanjI由加法法例:IanjIal=2an1二11,()求解an=2n-1【例】(Lancaster戰(zhàn)斗方程)兩軍打仗，每支軍隊(duì)在每日戰(zhàn)斗結(jié)束時(shí)都盤點(diǎn)人數(shù)，用ao和bo分別表示在戰(zhàn)斗打響前第一支和第二支軍隊(duì)的人數(shù)，用an和bn分別表示第一支和第二支軍隊(duì)在第n天戰(zhàn)斗結(jié)束時(shí)的人數(shù)，那么，an1—an就表示第一支軍隊(duì)在第n天戰(zhàn)斗中損失的人數(shù)，相同，bn1—bn表示第二支軍隊(duì)在第n天戰(zhàn)斗中損失的人數(shù)。假定：一支軍隊(duì)所減少的人數(shù)與另一支軍隊(duì)在每日戰(zhàn)斗開始前的人數(shù)成比率，則a'"bn-1 an Abn4「1bnBan1常量A、B——胸懷每支軍隊(duì)的武器系數(shù)aaan nr Abm1 ()bn n-1 Ban1——含有兩個(gè)未知量的一階線性遞歸關(guān)系組?！纠吭O(shè)an系。=4廣/廿，求｛2｝所知足的遞推關(guān)kLik【例】設(shè)an系。（解）x——下整數(shù)函數(shù)。即不大于x的最大整數(shù)。L」/n1嚴(yán)-1)產(chǎn)-2n為偶數(shù)：ann為偶數(shù)：an=2-I—I-n為奇數(shù)：ann--2n-1I0JI12-I—I-n為奇數(shù)：ann--2n-1分兩種狀況：當(dāng)n為偶數(shù)時(shí)，令n=2m，則2n1=n- =m-12mkk=02mm1r2m02mlmJ11k

rk=1k=02mm1r2m02mlmJ11k

rk=1m4+'k=12mk-k1/m)rk-p rm1/Im)前兩項(xiàng)乞降:f2m02mk1knr虧JrnIk=0Lkrk=akJ n一1后兩項(xiàng)乞降:2mj=0m12mriI2mj=0m12mriIj=02-j〕JrJjJrJ十r -rm1m1m-1n-2n2J、.rEj rJ=ran2jo?janan1+ran2當(dāng)n奇數(shù)也成立。求初：a0=a1=1。a2=a1+ra0=1+r,a3=a2+ra1=1+2r,a4=a3+ra2=(1+2r)+r(1+r)=1+3r+r2a5=a4+ra3=(1+3r+r2)+r(1+2r)=1十4r十3r2【例】0出偶數(shù)次的n位八制數(shù)共有an個(gè)，0出奇數(shù)次的數(shù)共有bn個(gè)。求an和bn足的推關(guān)系。0出偶數(shù)次的n位八制數(shù)分兩種狀況：(1)最高位是0,其他n-1位含有奇數(shù)個(gè)0,八制數(shù)共有bn1個(gè)。_(2)最高位不是0,其他n-1位含有偶數(shù)個(gè)0,八制數(shù)共有7an1個(gè)。 .所以有an=7an」+bn1。同理可得bn=@人1十7bn1,所以an、bn足,|an=7an_1bn_1bn-7bn-1an--[a1=7,b1=1例n=20出偶數(shù)次的數(shù)00,11,12,13,14,15，…，77,共50個(gè)0出奇數(shù)次的數(shù)01,10,02,20,03,30,…，70,

y_yx，共14y_yx，【例】用退后的Euler公式求常微分方程的數(shù)解。(解)函數(shù)y=y(x)在點(diǎn)xn的真y(xn),近似yn，求數(shù)解即利用數(shù)方法求y(x)在xn的近似yn(n=1,2,……)。思想:以直代曲。向前的Euler方法：yn1=yn-hfxn,yn，此中h=xn1-xn稱步。//(Xji+1,Yn+1)(xu,y(xn)l^___J—— A向后的Euler方法:退后的Euler公式是指常微分方程y，=f(x,y，當(dāng)已知函數(shù)y在xn的，可通解代數(shù)方程yn(i=yn.hfxn.i,yn.1求得函數(shù)y在xn.1的數(shù)解yn.1,此中h=xn1—xn是自量x的步(n=0,1,2,…)。

已知原方程為y,=fx,y=y_2_，代入Euler公式可得函數(shù)y的數(shù)值解為?yn1=yn+h「yxn1y十n1（五）本章研究內(nèi)容h「yxn1y十n1（五）本章研究內(nèi)容1.2.建模;求解。系數(shù)線性遞推關(guān)系常系數(shù)的線性遞推關(guān)系:anC1an1c2an2'"ckank二0,ck"0 °anc1an1c2ac.kaanc1an1c2a遞推關(guān)系和k階非齊次遞推關(guān)系。此中f（n）

稱為自由項(xiàng)。明顯，式（）起碼有一個(gè)平庸解an0n0」,2,,而人們更關(guān)懷的是它的非零解。結(jié)論：對于常系數(shù)線性遞推關(guān)系的定解問題，其解必是獨(dú)一的。,求解方法：首推特色根法。思想：根源于解常系數(shù)線性微分方程，因?yàn)槎咴诮Y(jié)構(gòu)上很近似，所以其解的結(jié)構(gòu)和求解的方法也近似。的性質(zhì)【性質(zhì)1】設(shè)數(shù)列」和，b【性質(zhì)1】設(shè)數(shù)列」和，bn2 ,）的解，則、r1bn1數(shù)。r2bn2'也是（）之解。此中r1、r2為隨意常（證）！bn13、，：bn2）知足方程（），即k1■■In

bkCkk1■■In

bkCkC2_Jin2c十12_1c十

2

(n

b令r1X①+r2X②得：TOC\o"1-5"\h\zk k krrcibnli-r2Xcibn3i—‘cir1bnJLr2bn2i=0i=0 尸0 尸0（規(guī)定C0=1,下同）?！就菩小吭O(shè)bj）｝,Ln（p,…，bns）｝均為（）之解，s ，一一* ? ? ? 、則,bn二＜ribni也是（）的解。此加1,12， ，%為隨意i二1常數(shù)?！拘再|(zhì)2】設(shè)dni和d/是（）的解，則bndni凡2=是（）的解?！拘再|(zhì)3”若bn是（）的解，）dn是（）的解，則；dn二bn）是（）的解。一般情況：設(shè),;dn渥（）的解，bn1,bn2.）,,,bn.s:）■ s ,分別是（）的解，則 .dn.、bni:是（）的解?！拘再|(zhì)4】設(shè)"心）是遞推關(guān)系、kCa.=f1n的解，，;dnn ini n2i=0k是遞推關(guān)系zCian—=f2（n的解，則dn=d1i）+d/2?是遞i0TOC\o"1-5"\h\zk f推關(guān)系Zcian （n）+f2（n的解。nT?1 乙i=0§3.2.2解的結(jié)構(gòu)（一）觀點(diǎn)an,cian」-c2an2 …ckan_k=0,ck-0 （）【定義】稱多項(xiàng)式\o"CurrentDocument"C（x）=xk.cxk1.cxk2 cxc1 2 k1k為齊次遞推關(guān)系（）的特色多項(xiàng)式，相應(yīng)的代數(shù)方程C（x）=xk.c1xk1c2xk-2.....ck1x.ck=0稱為（）的特色方程，特色方程的解稱為（）的特征根。（二）結(jié)論【定理】數(shù)列anqn（）的非零解的充足必需條件是q為（）的特色根。（證）an_qn是（）的解=qnciqn-1 Ckqnk=0=qkciqk-1 ck=0二q是方程C（x）=0的根，即q是（）的特色根。意義：將求解常系數(shù)線性齊次遞推關(guān)系的問題轉(zhuǎn)變成常系數(shù)代數(shù)方程的求根問題，進(jìn)而給出了一個(gè)適用且比較簡單的解此類遞推關(guān)系的方法。（三）通解【定義】若：1…2；_ ，渥（）的不一樣解，且（ an）,的任何解都能夠表為rian1r2an2 ,rsans=an，則稱an為。的通解。其中ri,r2,,rs為隨意常數(shù)。此地方說的不一樣解是指將每一個(gè)解ani都視為一個(gè)無量維的解向量，而這些向量之間是線性沒關(guān)的。說明通解的特色：①通解an第一是解；②構(gòu)成通解的所有解向量線性沒關(guān)；③任何一個(gè)詳細(xì)的解都被包含在通解an中?！?.2.3特色根法思路：經(jīng)過解式（）的特色方程，求得其特色根，再利用特色根結(jié)構(gòu)（）的通解。

（一）特色根根情況q1,q2,，,qk是（）的互不相同的特色根，（）的通解anAlQlnA2q2n Akqkn （）此中A1,A2,,Ak隨意常數(shù)（待定）。?W弓（）（1）an是（）的解：由定理3.2.1知qin是方程。的解，再由性1知an也是（）的解。（2）向量q產(chǎn)，q2n， ,qkn性沒關(guān)：（）（ 。的所有解都能夠表（ ）的形式：bn3是（）的一個(gè)解，且足初始條件bi di,i=0,1,2,k =k—1。令bn程Aiqink—1。令bn程二i1AqF A2q20 Akqk0b0A^ A?q2 Akqk二?|++…+__, A1q1kji&q2k1 Akqkk1bk1系數(shù)隊(duì)列式范德蒙隊(duì)列式:一’一二-1 1 1q1 q2 qkDq12 Dq12 q22q1k1 q2k1%2 qjqi=1ink( -qkk1<<<<所以式（）有獨(dú)一解。即b;必定能夠表示（）的形式。因?yàn)閎n的隨意性，故知成立?！纠壳筮f推關(guān)系an ―4an」+a?=—6a心的通解。（解）特色方程為x3.4x2.x.60，解之得特色根q1=-1,q2=2,q3=3???通解為an二A-1n-B2n-C3n此中，A、B、C為隨意常數(shù)。假如定解問題，設(shè)初值為：a0=5,a1=13,a與35,帶入通解得ABC5-A2B3C上13A4B9c二353一解得A=0,B=2,C=3，故an=2-2n33n=2n1-3n1若初值為a0 1=—, 2=，貝U=41 1 7an=3-1n 2n求A、B、C的方程組為ABC=4_A.2B3C=_1IA4B9c=7L規(guī)律：（二）重根情況【例】求遞推關(guān)系an _4an」.4an?=0的通解。

（解）特色方程x2.4x?4=0特色根 q1=q2=2（二重根）仿單根情況 an=A12nA22n=A1A22n=A2n一個(gè)待定常數(shù)。問題：知足兩個(gè)初始條件a0=d0,a1=di不太可能。本質(zhì)：兩個(gè)解向量ani=2n和an2=2n是線性有關(guān)的。任務(wù)：找兩個(gè)線性沒關(guān)的解向量，-和an2。另一解：令an2.n2n，也是解，且與ani=2口線性沒關(guān)。an-4a4（n1）2一1+4（n4（n1）2一1+4（n—2）2nLa。1）aia。2]a120=22通解：an.A12nA2n2n（需證明）一般情況：設(shè)q為k重根，則通解為an二A1-A2n二 -Aknk1qn更一般的情形：有t個(gè)根，qi為ki重根f t ）i1,2,…，t;zki=k，通解i-1tkian=、、Aijnj1qinAi1廣1=t 11+A12n+…十A1knk「1）qj1，，A21 22n, &k2n^1q2n“At2n%nkt」qnt【例】求an -7an_1 19an._2-25an_316an_4_4an5=0的通解。（解）特色方程x5-7x4-19x3-25x216x-4=0特色根： x=1（三重），x=2（二重）通解an=(A]]+A]2n+A]3。2)1n+(A2]+A??。)2n=(A11+A]2n+A]3n2)+(A21+A22n)2n（三）復(fù)根情況設(shè)特色方程有一對共軛（單）復(fù)根：q二1門，；en,則通解中含AqnBq=A二nein"B1"ne；n=APnIcosn0)+isin(n0)1+Bpnbosn9)_isin(n6)]=A B'二ncos.n二+iA_B：-nsinn二=A1Pcosna)+A2Pnsin(n6)n通解：an=A]ncosn。,A2:nsinn1r長處：防止了復(fù)數(shù)運(yùn)算。特別是當(dāng)數(shù)列 {an}是實(shí)數(shù)時(shí)，nAqn-Bq的虛部為零。一般情況：q是m重復(fù)根，-也是m重復(fù)根，通解中有PkA1+A2m…十Amnmi)cosn0+■(B1+B2/…+Bmnm^jsinn9)」小結(jié)：特色根通解中對應(yīng)的項(xiàng) 一實(shí)根q為單根Aqnm重根(A1+A2n+…+Amnm1qn復(fù)根對單復(fù)根q=Pei",q=Pe十?PlA1cosn9)+A2sin(n日)1一對m重復(fù)根q=peis,q=Pe”pn(A1+A2n+…+Am/])cos(n。)+(++…+一)(日)B1B2n Bmnm]sinn【例】求定解"an-2an1+2an2（解）特色方程:特色根：q2

= ..q24a0二0,a1二（方法I）按復(fù)根形式:通解:an「2n代初：解：A=0,B=1定解:anAcos71sin714n3TRa12+b」2=2f—JV2 2,nsinJL丁4m=1m22m2m,當(dāng)n二4m1+1,當(dāng)n34m2,4m,m=0,1，…數(shù)列：0,1,2,2,0,-4，-8，-8,0,16,-32，-32,AA」2iB二一2（方法II）按根形式:通解： an=A1inB1-inTOC\o"1-5"\h\z代入初： A.B=0 ，即1iA.1_iB=1定解： an=-11in.L1-in2 2化復(fù)數(shù)表示形式數(shù)形式an=_i("￡“C0s」+isin」！I 14>cos22"isinisin(V)sinn【例】求定解；an—(4+ian1+(5+4ian2-(4+5i0n3+(4+4i可口4-4ian$=0Ia0=5,a1=6,a?=10,a3-24,a4=50(解)特色方程：q5-4iq4 54iq3_4-5iq2. 44iq4i=0特色根： q=2,2,i,i，一i通解： an=(A+Bn2n+(C+Dni)n+E—inACE=52-AB)+(CD-i+E(i)6=代初：j4-A+2B)_(C+2D)_E=108-A+3B)_(C+3Di+Ei=2416A4BC4DE二50解：A=3,B=0,C=1,D=0,E=1定解:an=3,2n+in+(")定解:n32n21n/2,當(dāng)n4m,4m2“+(-)二+32n,當(dāng)n二4m1,4m 3n=0,1,…（四）代數(shù)方程求根方程：anxn-an1xn1 a1x-a0=0,在復(fù)數(shù)域上必有n個(gè)根X1,X2「，Xn（k重根按k個(gè)算）。

x1x2…x1x2…xn（1）韋達(dá)定理（）推論：例2x1 x2…xnnaoanan4an中，方程342 60如有整數(shù)x-xx二根，則此根必整除-6,即此根必為土1,土2，土3，土6之一。（3）方程的降階：由韋達(dá)定理知-1是解，方程必可分解為x1x2axb=0§3.2.4非齊次方程（一）結(jié)構(gòu)困難性：與微分方程近似。()()可解情況：f（n）()()anC1」-C2an2'-ckanaC2an2Ck」【定理】設(shè)a*n是（）的一個(gè)特解，an是（）的通解，則（）的通解為aFanan（證）（1）an是解；（2）an是通解。（近似齊次情況）意義：問題歸納為求非齊次遞推關(guān)系的特解。（二）待定系數(shù)法目的：求特解an*困難：無一般通用方法特例：當(dāng)自由項(xiàng)f（n）比較簡單時(shí)，采納待定系數(shù)法（一）f（n）=b（b為常數(shù)）a：Anm

nm表示1是m重特色根。若1不是特色根（即m=0），則a*n=A。（二）fn=bn（b為常數(shù)）an*=Anmbnm表示b是m重特色根。若b不是特色根，則an*=Abn。（三）fn二bnPrn，此中Prn為對于n的r次多項(xiàng)式，b為常數(shù)。an*=nmbnQrnQrn是與Prn同次的多項(xiàng)式，m是b為特色根的重?cái)?shù)。當(dāng)b不是特色根時(shí)，a*nbnQrn。.（三）例【例】求非齊次方程an—13an_2+I2an_3=3的通解。（解）剖析：方程右側(cè)為常數(shù)3特色方程： q3—13q+12=0特色根： q=1,3,-4,m=1特解：an*=An（A稱為待定系數(shù)）代入遞推關(guān)系：An—13A（n—2）+12A（n—3）=3整理得 一10A=33解之 A=，故為10通解：an=B1+B2n+B3— n—3。此中1、B2、B3為任" 3 （4）%n B意常數(shù)?！纠壳筮f推關(guān)系an—4an1+4an2=2口的通解。（解）剖析：方程右側(cè)為2n

特色根：q=2(二重根)，特解： an*=An22n代入原式：An22n-4An-122n1+4An-222n\=2n睜開：An22n-2A(n2-2n+1)22n+A(n2-4n+4)22n=2n整理： 2A2n=2niTOC\o"1-5"\h\z待定系數(shù)： A=_2\o"CurrentDocument"一 一'一.1- C通解：an =Bi2n +B2n2n +n22n =B] b2n」n22n。2 2此中B]、B2為隨意常數(shù)?！纠壳骯n+4an_1+an-2=n(n—1)的通解。(解)剖析：方程右側(cè)為多項(xiàng)式：f(n)=n2-n(b=1)特色根：q=-2±,T(b=1不是特色根)特解： an*=An2+Bn+C代入原方程：An2Bn-C+4An-12Bn-1=C+An-22Bn-2C=-

n(n1)整理：6An2-6(2A-B)n+2(4A-3B+3C)=n2-n比較兩邊同類項(xiàng)的系數(shù)：6A二1-62A-B二—12(4A—3B+3C)=0TOC\o"1-5"\h\z\o"CurrentDocument"1 1解得A= ,B= ,C= 16 6 18通解：an通解：an=3n1。此中、B為隨意常數(shù)。（四）化非齊次方程為齊次方程n【例】求sn=、k。n二Sn40=0n,（解）（n二Sn40=0n,系注：不可以用迭代法求解。(2)化為齊次遞推關(guān)系改寫遞推關(guān)系TOC\o"1-5"\h\zSnn1n ①近似得sn1n2n1 ②①一②得sn2sn-1sn飛 1 ③同理s--2ss.二n1 n2n3 1 ④一 一s 二③一④得 sn3sn1 3sn2n30,s00,s1 1,s2 3規(guī)律：左側(cè)升階，右側(cè)降階。（3）求解特色根：q=1是三重根。sn=ABnCn21n=ABnCn2

代初值(s0=0,s1=1,s2=3)：A=0ABC二1

++—A2B3C3

1，A=0,B=C=「?Sn_1nin2=nn1）

2 2 2用遞推關(guān)系證了然乞降公式nn11.2 .n.2（五）一般乞降公式n（1）問題：求S.r=「krnk=0（2）化為齊次遞推關(guān)系求解第一，當(dāng)r=1時(shí)，由（四）知sn二ABnCn2當(dāng)r=2時(shí)，可得snn^_1Sn-n-2=nsnn^_1Sn-n-2=n12①一②得 1sSn-2sn_1- n2=2n1ssn-3=2n1sn-1-2sn-2,③—④得 2sn-3sn_13sn_2-口工11s_- _ _s=n1 3$口2 3$口3n4 1⑤一⑥就得對于sn的齊次定解問題①②③④⑤⑥1,1,(3)迅速求常數(shù)A、B、C、D等當(dāng)r=1時(shí)，令sn=A；!-Bn-Cnn-1A二0代入初始條件后得 A?B=1A2B2c=3解得A=0,B=1—A=1,C=1——=1TOC\o"1-5"\h\z_(3A2B) —2 2???sn=n-nn.1=nn1—2 2長處：不需要解線性代數(shù)方程組，即可逐漸遞推地解出系數(shù)A、B、C等。另法：令」.刖一A=0代入初值條件 AB=1A2BC3L解得 A=0,B=1—A=1,C=3—A—2B=1長處：在利用初值確立A、B、C時(shí)更為方便。因?yàn)榉匠讨蟹謩e對于A、B、C的系數(shù)恰巧是1,不做除法。當(dāng)r=2時(shí)，可令sn-ABncUDnn-1n2

2! 3!代入初值(s0代入初值(s0=0,s1=1,s2=5,s3=14得方程組A二0TOC\o"1-5"\h\zA B二 1A 2B C二 5A 3B 3c D= 14IA=0,B=1,C=3,D=2s…3nn112(nn1n)2nnJ2n1+2 6 6對于較大的r，求部分和snr時(shí)，利用非齊次遞推關(guān)系ssnr求解仍是要比將其化為齊次遞推關(guān)系方便得二■,nn1（4）一般情況若通解an為r階多項(xiàng)式Prn,）對定解問題（），可令fnI /n\P4n）=A+A|+iIr0IJ1一使得用初值條件求解常數(shù)A特別簡單。一般遞推關(guān)系化簡對于某些非線性或變系數(shù)的遞推關(guān)系，能夠?qū)⑵浠癁榫€性關(guān)系來求解?！纠拷舛ń鈫栴}.an-nen2an-1=0，

a0=1.【例】解定解問題（解）線性變系數(shù)一階齊次關(guān)系。改寫兩邊取對數(shù):lnan令b兩邊取對數(shù):lnan令bn=lnanaan=nen2n」=lnan4-lnnn2_b=lnn n2,n1二0.再令f1(n)=lnn,f2n二n2。化為兩個(gè)遞推關(guān)系?b「“口―n-1-Inn,和jbn—bc=n2,b0=0. b°=0.用迭代法解［用迭代法解［bn-bn」=lnn，b0二0.用待定系數(shù)法解 n-b一二n1b0二0.進(jìn)而得，得bn1=lnn!，n2,，得12sn(n+1(2n1。6bn=Inn!nn1"2nlnn!■+~nn1卞nh*) n[12(n1*TOC\o"1-5"\h\z6 Inn! 6ennf2ne1an_n!exp :I= _ 6【例】解定解問題nann-1an1=2n，n-1

a0二273.【例】解定解問題（解）線性變系數(shù)一階非齊次關(guān)系。bn-bn1-2n,令bn=nan得通解為bn二B?一1n由初始條件b00知B_2-一32-2—1n.2^22-nan3 3二212n__1n], n13na0=273.即a1一【例】解定解問題

an_nan1二n!,na2-a。二2.（解）線性變系數(shù)一階非齊次遞推關(guān)系。難點(diǎn)：f,n,二n!an ai…士 ——-n^=1,n1察看：n!n-1!|ao=2bb二1,n上1令bn=an，化為一nn4 ,一n! bo=2特解：bn*=n，通解：bn=B.1n nan的通解： an=n,2n!.另法：對于bn，能夠用迭代法或直接察看出b=n2，n再用概括法證明之即可?！纠吭O(shè)n三1時(shí)，an》0，解定解問題an2_2an2 1,n1■ 。a0=2（解）常系數(shù)非線性二階遞推關(guān)系。令上;寸，變成：bn-2bnj1,nF,b0=4 解之得bn=52n-1,進(jìn)而an=..52n-1。遞推關(guān)系的其他方法代法與概括法適應(yīng)狀況:

.迭代法：某些一的推關(guān)系，使用迭代法求解可能更快。.法：察n比小an的表達(dá)式的律，或猜出an的一般表達(dá)式，而后用法明。IaIan-2an12n,11【例】(解)a0=3an2【例】(解)a0=3an2n逐漸迭代:ani2nian2^an-22n-2a020 n=n3an=2nn3,n1當(dāng)n=0，上式仍成立（即足所的初），故解an=2nn3;n-0另法:先做量代bn二an(n=1,2,…)，得2nbbn=n-1,1,n-1b0=3迭代求解： bn-n3,n一0TOC\o"1-5"\h\z而后反代回去得a=2nb=2nn3, .n1\o"CurrentDocument"n nan二nan1-1n, n-1【例】解推關(guān)系 c一a0二3J(解)因 an=&1-二IL,n_1n!(n-1)!n!

迭代得ann2 1 (—In迭代得 ==—1 1 n!(n2)! (n1)!n!0! 1! 2!0! 1! 2!-1n

n!所以1kon所以1kon- -32、 二二k!k1'nan二n!2'Zk01k3,n建k!當(dāng)當(dāng)n=0，上式仍成立，故定解的解anan=n!In2」k(-1”、o^Tj【例】解遞推關(guān)系a【例】解遞推關(guān)系an=4anja0=2,2，n-a1=1（解）由a二二二二2k1 22a2k124a2k3 22ka1a= = = =2k22a2k2 24ak-4 22ka0a所以 2k■122k，a2k22k1，k1當(dāng)k=0，上邊兩個(gè)式子仍成立。故-當(dāng)n為奇數(shù)二2n1,時(shí)當(dāng)n為偶數(shù)2n1,時(shí)或 an2n=1n一，n0【例】用法解推關(guān)系 [n-n1+n1《之）a0=0（解）算小n的an，并察得@0=0=02a1=1=12= 1 02a2=13. 23=9= 0 1- 22a3=132333二36二：01232 由此可猜想2an=01.2...n2 ?nJI_n二n21n22 4再用法之：然n=0,1,2,3 真。假n=k真，即ak= 21k'成立。24考n=k+1ak.1=ak：k13=k21kP上,kJ3、（k12（k與2 +（4）二 4 4成立。故全部非整數(shù)n，有an=n2 -n2。4§3.3.2母函數(shù)方法思路：復(fù)的推關(guān)系，利用母函數(shù)求解。方法：

CG設(shè)欲求解的數(shù)列｛an｝的母函數(shù)為G(x)=anxn；CGnq利用遞推關(guān)系自己求函數(shù)G(x)知足的方程(代數(shù)方程或微分方程等)；解方程求出G(x)；將G(x)睜開成x的冪級數(shù)。則xn的系數(shù)即是an的分析表達(dá)式(即遞推關(guān)系的解)?！纠拷膺f推關(guān)系an—5ani+6an2=2n,n三2(解)(利用無量乞降)：令A(yù)(x)=-anxn，原方程兩邊同乘xn得n=0an-5an1--6an_2,xn二2nxn即 anxn-5anJxn-6an2xn二2xn6aan2oC入anxxn-5a6aan2oC入anxxn-5anT—5 an1xn+6a_2/)=N(2xnn2□c oOxn+6an2xn=、2xnn2aanxnn二2oC5xann2xn+6x2%anxnn2 n1 n=0 n=2i(A(x)—ao—aix)—5x(A(x)—ao)+6x2A(x)=—(1+2x)1-2x解之得a0a1-5a0x 4x2A(x)= 15x+6x2f15x^6x2X1—2x)A(x)=c1 .c2 . -21-3x12x1-2x2

將A（x）睜開A(x)=c1.3xn+cf2xn-2CO=7CO=7n=0C13n+C22n—(n+1)naC='anXn=0比較等式兩頭劃的系數(shù)an=c13n+c22n-(n+1)2n1式中ci、。2為隨意常數(shù)，由初值的和冉確立。比如，設(shè)a）=1,ai=-2,貝Uci、C2知足以下方程組c1,c1,c2-3cl2c2-8=-2解得。1=0,。2=3.所以知足上述初值條件的遞推關(guān)系的解為an=3x方一(n+1)方?1=(1-2n)2【例】求定解問題F【例】求定解問題FnFF[=+n一1 ￡2F1=F2=1（解）（思路：拆項(xiàng)）。反推求Fo=F2-F1=O設(shè){Fn的母函數(shù)為}依據(jù)遞推關(guān)系有

G(x)=0+x+' Fn1-Fn_2xnn26 OO=x+X。Fn1xn』+x2-<Fn_2xn-2n=2 n=2G(x)=x+xG(x)+x2G(x)()x()G(x)= xx2利用“待定系數(shù)法”睜開G(x)2利用“待定系數(shù)法”睜開G(x)為冪級數(shù)，A B + 1 1 5x11-5xTOC\o"1-5"\h\z2 1A+B)+f^5-1A_75+B】xG(x)=12一2 G(x)=j1_1_亞x!|Z1_1+x!〔一2A-2JAB=0得A、B應(yīng)知足的方程5TA7?1b1 .- -2 2解之得 A=_，B=—5 一.5JG(x)j1 1 _ 115 1 1丁 5x1 1%5x |一 一2一2\o"CurrentDocument"I I睜開G(x)，令'1-5 ,；； 1--52 2

G(x)=acZ(8

n ..xn「ixG(x)=acZ(8

n ..xn「ixxn一Fn1n..—-P,51—5-1<52，明：此有名的Fibonacci數(shù)列（§3.4）。一個(gè)事，然Fn都是正整數(shù)，但它卻可由一些無理數(shù)表示出來?！纠?】解定解n1an-n2an12an二=0,n2-。ja。二0,a1二1（解）依據(jù)方程的特色，令A(yù)(x)=a]+a2x+a3x2+a4x3H banxn1兩x求A'(x)=2a3x+3a4x2H b(n-1)anxn2(注意由原知a2=0),算A'(x)-xA'(x)，得(1—x)A'(x)=2a3x+(3a4—2a3)x2+(4a5—3a4)x3—+[(n-1)an—(n-2)an」]x-2+…=2a1x+2a2x2+2a3x3H H2an2E2一…=2xA(x)(注意原方程可化 (n—1)an—(n—2)an1=2an2,a3=a1)A'x=2x=—2+2xA(x)A(x) 1-x1-x注意到Ax.二注意到Ax.二a1x-0Ax=1,兩邊對x積分得0A(X)dx=-2x—2ln(1—x)lnA(x)+ln(1—x)2=—2xA(x)=e—x/(1—x)2展成冪級數(shù)A(x)=IAn0二nA(x)=IAn0二n|ZI；一一.n0k(02xnn!,n0-1k2kn.k1nan+1=x/k,-1，n(k12

k!k0【例】（用指母函數(shù)求解）：求解遞推關(guān)系Dn二nDn」-1nn2D1=0（解）由原方程反推可得D0=D1—（—1）0=1。察看：Dn隨n的增大而急劇增大，有點(diǎn)象n!，故用指母函數(shù)。D(x)=xDnxn二n!用」乘以原方程的兩頭，n!n0并對nD(x)=xDnxn二n!用」乘以原方程的兩頭，n!n0并對n從1到8乞降，得nDn:n!+■心 xn??一 n一二1n!與母函數(shù)比較亦即D(x)—D0=xD(x)+eD(x)=-x1-x由母函數(shù)的性質(zhì)3nn!z——

k=0k!Dn由母函數(shù)的性質(zhì)3nn!z——

k=0k!Dn=n!11 1——+1!n12!n!【例】用母函數(shù)方法求解二@n二3abn二ann_12bn1_1bn_1a0=1,b0=0（解）設(shè)數(shù)列an、化口）的母函數(shù)分別為A（X、B（解）設(shè)數(shù)列an、化口）的母函數(shù)分別為A（X、BX。方程一兩邊同乘以Xn得anxn=3anlxn2bn_1xn兩邊對乞降： 、anxnn=1oO=3xan1xn1n12xxbnlxn1n1A(x廣a0=3xAX十2xBx()代入初值并整理：同理，由方程二可得代入初值并整理：同理，由方程二可得(1-3x)Ax—2xBx=1xAx+(x—1)Bx=0聯(lián)立方程①、②解之TOC\o"1-5"\h\z1- x尸 1-4x■- x214xx2函數(shù)分解:J r.1-2 3jrBx.=36jrBx.=361一冪級數(shù)睜開--3 61一21ifirVAx3n-32n-non0c-366.336-3(2(2_,3)Ax3n-32n-non0c-366.336-3(2(2_,3)-3（2、3「）

X(2..3)種典型數(shù)列Fibonacci數(shù)列、Stirling數(shù)列和Catalan數(shù)列常出在合數(shù)中，是比典型的三種數(shù)列。其典型性不在于數(shù)列自己，是在于多數(shù)的算關(guān)系都與三種數(shù)列是相同或相像的。Fibonacci數(shù)列（一）背景定:序列1,1,2,3,5,8,13,21,34，…中，每個(gè)數(shù)都是它前二者之和，個(gè)序列稱Fibonacci數(shù)列。意義：因?yàn)樗谒惴ㄆ饰龊徒碇衅饌?cè)重要作用，又擁有很奇異的數(shù)學(xué)性，所以，1963年起美國就第一版了一數(shù)列行研究的季刊《FibonacciQuarterly》.根源：1202年由意大利有名數(shù)學(xué)家Fibonacci提出的一個(gè)

風(fēng)趣的兔子：有雌雄一小兔，一月后大，兩月起今后每個(gè)月生（雌雄）一小兔。小兔亦同這樣。一月份只有一小兔，一年后共有多少兔子？一般化：n個(gè)月后共有多少兔子？Fn=FnFn=Fn1Fn2,n3F1=F2（3.4.1）1.第n個(gè)月的兔子數(shù)Fn,Fi=F2=L月份 ……一一n1234n2n1n1小兔子婁攵111F01n_2大兔子數(shù)112Fn2Fn_2F11n_1數(shù)1123Fn1FnFn=前一個(gè)月兔子數(shù)十本月新增兔子數(shù)=Fn1+Fn2（二）求解或FnFnn為偶數(shù)或FnFnn為偶數(shù)n為奇數(shù)（三）用【例】（上樓梯）某人欲登上n樓梯，若每次只好跨一或兩，他從地面上到第n樓梯，共有多少種不一樣的方法？（解）上到第n樓梯的方法數(shù)an。分：（1）第一步跨一，余下的n―1有an_i種上法；

（2）第一步跨兩，余下的n—2有an2種上法?！竌 a…n、3由加法原理n=n1- n2,n-（反推得a0J）。al=1,a2=2.FlFFlF2F3F4F5F61 1 2 3 5 8analaanala2a3 a4 A5—n1fi-C]【例】（棋染色J）一個(gè)擁有1行n列的1Xn棋（）的每一個(gè)方涂以、二色之一，要求相的兩不可以都染成色，不一樣的染法共有 an種，求aan。123n1n圖3.4.11Xn棋盤（解）分，格子1的染色有兩種可能:（1）染色:染色方式數(shù)=1X1Xan2=an2；（2）（2）染色：染色方式數(shù)=1Xan_1=an_1.aan=n'+an_2,n3（a1）由加法原理a1-2,a2-3.F1F2F3F4F5F6112358a1 a2a3a4- n2 n2， r/an=Fn70I1^^-1^^I55K2)I2JJ似：無兩個(gè)1相的n位二制數(shù)共有Fn2個(gè)?！纠?交替子集)有限整數(shù)會(huì)合Sn =口,2,\n的一個(gè)子集稱交替的，假如按上漲序次列出其元素，擺列方式奇、偶、奇、偶、…。比如｛1，4，7，8｝和｛3,4，11｝都是，而｛2,3，4，5｝不是。令gn表示交替子集的數(shù)量(此中包含空集)，明gngn1 gn2且有g(shù)nFn2, 二- -()■初：g1 2,S1的交替子集中和｛1｝。g2=3,S2的交替子集①、｛1｝、｛1,2｝。剖析:將Sn的所有子集分兩部分：Sn1 1,2, ,n1.的所有子集；Sn1的每一個(gè)子集加入元素n后所得子集。例：n=4,S41,2,3,4的所有子集區(qū)分兩⑴①、｛1｝、｛2｝、｛3｝、｛1,2｝、｛1,3｝、｛2,3｝、｛1,2,3｝(ii)｛4｝、｛1,4｝、｛2,4｝、｛3,4｝、｛1,2,4｝、｛1,3,4｝、｛2,3,4｝、｛1,2,3,4｝第一部分，即Sn1的交替子集數(shù)gn1第二部分中的交替子集2 1,27,n2的交替子集，有g(shù)n2個(gè)。關(guān)系Sn -2的交替子集加上n或n與n—1即可。 _

加入，，去掉，343434二g1，2,3,4：加入，，去掉，343434二g1，2,3,4：1 14去掉4 去掉3,4的推關(guān)系gn二g52nn1n2_F??? 解與例同g一n'2n【例】（棋的（完整）覆蓋）用格1X2的骨牌覆蓋pXq的方格棋，要求每骨牌恰巧遮住上的相兩格。所完整覆蓋是指棋的一種覆蓋（即上所有格子都被覆蓋），并且骨牌不相互重疊。簡單看出，必定存在2Xn棋的完整覆蓋。在的是，終究有多少種不一樣的完整覆蓋方案？（解）所求方案數(shù)gn。最左面的四格有且有兩種可能的覆蓋方式：（1）一骨牌著放:等價(jià)于2X（n—1）棋的完整覆蓋，有由加法原理?由加法原理?gn=gn」gn2，j — —I（2）一骨牌橫著放:等價(jià)于2X（n—2）棋的完整覆蓋。有1X1Xgn2種方案。.g1=1，g2=2.gn,1§3.4.2Stirling數(shù)列(一)Stirling數(shù)(1)下階乘函數(shù)Xn[】=xx1x2，lx0(2)遞歸定義ixnixnix-n-10二1(3)(下階乘函數(shù))與冪函數(shù)的關(guān)系：相互表示「XX二1二X0，01nx，二X2-X，2二x3一一3x2■2x3x0二lx0，LX」1X」LX」3二[xgIX4=X4-6X3-11X2-6x，x4=&4+6jx3X2,x3-3X2(4)Stirling數(shù)【定義】設(shè)十1X2x:3x2-3xxx二n nIxn=ES](n,kxk，xn=2S2n,k)x[k0 k=0則稱S1n,k、S2n,k分別為第一類和第二類Stirling■7X2+3x2+X111數(shù)。數(shù)列S1n,kk0-n的普母函數(shù)即為下階乘函數(shù)xn，其基函數(shù)為xn。反之以xk為基]函數(shù)，定義一種母函數(shù)，數(shù)列S2n,kk：0?n的這類母函數(shù)就是xn.(二)組合意義一一等價(jià)定義(1)分派問題：將n個(gè)有區(qū)其他球放入m個(gè)相同的盒子，要求各盒不空，則不一樣的放法總數(shù)為S2n,m；(2)會(huì)合的區(qū)分：將含有n個(gè)元素的會(huì)合恰巧分紅m個(gè)無序非空子集的所有不一樣區(qū)分的數(shù)量即為S2n,m。這類區(qū)分也稱為會(huì)合的m—區(qū)分。(三)性質(zhì)【定理】第一類Stirling數(shù)的性質(zhì)：S1n,0=0，S1n,1=(n-1)!一1n-1,S1n,n=1，S1n,n-1=-Cn,2、,)sgnS1(n,k))=(—1)n：，(6)S1n,k知足遞推關(guān)系S1n,k=S1n-1,k-1n1S-rn.1,k(證)由(xn的表達(dá)式即知(1)?(5)成立。xn=x■x1X'2-…x-n1-,x01=41(6)由遞歸定義 [xn=(x.n+1&n1，左右各自睜開；Sn,kxk=xx]__(n」x]_n1 n1k=0n—1 n-4=x(S1n1,kxk-n1%S1n-1,kxkk=0TOC\o"1-5"\h\zn-1 nL=￡S1(n工kx)k"-￡(nLS)in1,kxkk-0 kO\o"CurrentDocument"n nL=￡S1(n」,kbjk—Z(n1S)1nLkxkk-1 k今n=￡IS1_n1,k1)-(n1S)1nLkx)kk=1比較等式兩頭同次冪的系數(shù)。利用si(n,k)的性質(zhì)，能夠像楊輝三角形那樣寫出第一類Stirling數(shù)值表(見表)。S2n,0二0，n>0；S2n,0二0，n>0；（4）S2n,1二)=S2n,n1=Cn2；S2n,2=2":一1；S2(n,k)=S2(n-1,k1kS2n(14(證)(1)—(3)，明顯。（4）n個(gè)球放入n-1個(gè)盒，各盒不空，必有一盒有兩個(gè)表S1n,k的數(shù)值表Xn、123451121132314—611—61524—5035—101【定理】第二類Stirling數(shù)有以下性質(zhì):

球。從n個(gè)相異的球中選用2個(gè)，共有C2n種組合方案。n個(gè)球，2個(gè)盒。任取某一球x，其他的n—1個(gè)球每個(gè)都有兩種可能的放法，即與x同盒或不一樣盒。故有2n1種可能。但要清除大家都與x同盒的情況（這時(shí)另一盒將空），故 --總的放法有2n11種。（6）從n個(gè)球中任選一個(gè)記為x，方案分兩類：（a）x獨(dú)占一盒：有S2n1,k 1種放法；（b）x不獨(dú)占一盒：第一步：其他n—1個(gè)球放入k個(gè)盒子，各盒不空，放法有S2n1,k種；第二步：將x放入此中某盒，放法有k種。由乘法原理，放法有kS2n1,k種。1 ?表3.4.2S2 a n,k的A數(shù)值表n12345112113131 ="41761511525101其他結(jié)論：（ ）=一Z）（(1(1)S2n,k1匕1iCk,ikink!i0-0<-=1k= 1kiCk,iin,k!.' ='i.0■ -p n(2)=in=k!Cp1,k1S2n,k.word(四)用【例】所有從｛1,2,二口—1｝中取n—k個(gè)不一樣數(shù)的之和是多少？比如，所有從｛1,2,3,4｝中取2個(gè)不一樣整數(shù)的之和是(n=5,k=3)1?2+1?3+1?4+2?3+2?4+3?4=35(解)和數(shù)f(n,k)，分：第一：含有因子n—1的。其和(n—1)f(n—1,k)，即從所有從｛1,2,…,n—2｝中取(n—k)—1=(n—1)—k個(gè)不一樣整數(shù)的之和，再乘以n—1得出。第二：不含n—1的。其和f(n—1,k—1)，即所有從｛1,2,…,n—2｝中取n—k=(n—1)—(k—1)個(gè)不一樣整數(shù)的之和。由加法法得fn,k.fn,k.fn.1,k_1使上式k=1和k=n—1都成立，定f,n,0二f,n,0二0,fn,n二1進(jìn)而有,f(n,k戶(fn1,k1)+(n1fnQ,k, )If(n,0 =0,fn,n=1.令gn,k.=-1nkf-n,k:，可得n根 nk_21)g(n,k-1g(n1,k1」)十(n11-1n%」gn[，k)fgn,k戶g(n1,k1一)一(n1gn4,k,)[gQ,0)=0,gn,n)=1.與S1(n,k)的性比，即知g(n,k)=S1n,k(。)「?fn,(k )=1—1nkgn,k)=S1n,k[【例】Stirling數(shù)的另一個(gè)重要用就是分派問題:馬上n個(gè)球(物體)放入k個(gè)盒子，其放法的數(shù)能夠分紅8

種狀況分別予以議論(見表)。表3.4.3.分派問題方案計(jì)數(shù)表空

盒是

否空

盒是

否不一樣的方案

數(shù)()+{S2n,1S2rkn-k!S2n,k-.n,2 S2n,r,=min(n,k) S2n,k C(n+k—1,n)睜開式中xn的系 C(n—1,睜開式中xn的系 1 一.一1.:k-1x1x2 1xkk-?睜開式中xn的系—k x說明：，上述8種情況不包含所有的分派模型，比如:(1)在情況1中考慮球的序次,)方案數(shù)應(yīng)為 )kk1k2kn1=Pkn1,n(2)對情況1,每個(gè)盒中最多只好放入一個(gè)球，方案數(shù)為Pkn，而不是kn。word§3.4.3Catalan 數(shù)歹.（一）定Cn1CCn1C1,

一 ()C C2n2m1nCn=C1Cn1-C2Cn2_C1=1.的數(shù)列稱Catalan數(shù)列。其解1,1,2,5,14,42,132,429,1430,4862,16796,（二）求解（解）母函數(shù)A（x）（解）母函數(shù)A（x），即AxQO=' CnXn,A2A2(x ECix.i1Y8 'L工CjxjAj /=C1C=C1C1x2+C1Cn1=Ax_x+C1C2-C2C1x3CC十…十2 n-2Cn[C/xn「. A2x_Axx=0A1x=1-14x,A2 x=1T,4x2 2因?yàn)锳(0)0，而A1(0=0,A20『0，舍去A](x)Axb」」).4*)1222利用泰勒睜開式f(x)=1_xrin01-2，f(x)=1_xrin01-2，-nTxnn!0Gh=Txn

■— nn!1 」 1Ax=—/―)+2、2 14x)222 1! 2!1fj_1f_L24x31fj_1f_L24x311352n3x- — 2

nl32

nl3

0cx-、 52n32n1(n1)!x n(2n-2)!x(2n-2)!xn(nT)!-n-1!1b一C2n2,n1,n1nn-2CC

― 旦n(n-1)!(n-1)!12n2!1（三）用【例】（凸n形的剖分）Euler在精準(zhǔn)算凸n形的不一樣的角三角剖分的個(gè)數(shù)，最初獲取了個(gè)數(shù)列。其是:將凸n形用不訂交的角分紅三角形，有多少種不一樣的分法？比如，五形就有五種剖分方案（）。凸五形的剖分方案(解)凸多形一指多形內(nèi)的隨意不相兩點(diǎn)的都在多形內(nèi)部。(1)求hn足的推關(guān)系凸n形的角三角形剖分的個(gè)數(shù)hn。然，n>3且卜31,h42。。 二當(dāng)n3,凸n+1形的點(diǎn)挨次v1,v2,…,vn+1，固定一條V1Vn1,再另取一個(gè)點(diǎn)vk(k=2,3,二口)，作三角形v1Vkvn1,它分多形兩個(gè)小的凸多形。一個(gè)是凸k形，其剖分?jǐn)?shù)hk，另一個(gè)是n—k+2形，其剖分?jǐn)?shù)hnk2(_(a)),由乘法原理和加法原理知3—n1()上2I.3—n1()上2I.n1n2hh2n隨意凸多形的剖分(2)求解令rn=hnj,得rn的定解

rn =Cn【例】P=rn =Cn【例】P=的擺列序，r二n.r1=11.n1 2n_2 … rn_111，.an個(gè)數(shù)的乘，保持本來1 2n有多少種不一樣的合方案（即依據(jù)乘法的合律插))入n—1括號，使得每括號內(nèi)恰巧是兩個(gè)因子的乘。如n=4,))P=a1a2a3a4=a1a2a3a4=….（解）剖析：Pn插入n—1 括號的方案數(shù)。于@建2…an的每一種合方案，其最后的那次乘法運(yùn)算，必是a1a2"ak的相乘果P1和ak1,…an的果P2兩相乘1?士kn1,即最外括號所含的兩個(gè)因子P1和P2。于固定的k,P1有Pk種不一樣的合方案，P2有Pnk種。.例子P=a1（（a2（a3（a4a5）帆》={P1P2,）P1=a1，P2=a2a3a4a5a6，P=a1a2a3-a4a5a6：=P1P2，.P1=a1a2a3''，P2=a4a5a6Pn=P1Pn1-P2Pn2 PnJP1，n3，P1=P2=]1.求解）n =Cn-C2n2，n1_。n事上，n個(gè)數(shù)乘的合方案與凸n+1形的三角形剖分是一一的。出了n=4的情況似的：在n乞降式中，不改各數(shù)的相擺列序次，只其插入括號，改乞降序，不一樣的合方案數(shù)也是Cn.

n=n=4時(shí)連乘積與凸5邊形三角剖分的對應(yīng)關(guān)系【例】擁有n個(gè)點(diǎn)的所有不一樣的二叉的個(gè)數(shù)是Cn.1-（解）特色:每個(gè)點(diǎn)都是一棵子的根，并且它至多有兩棵子。所以能夠定二叉點(diǎn)的有限會(huì)合，會(huì)合或許是空集，或許是由一個(gè)根（一個(gè)特定點(diǎn)）及兩個(gè)不訂交的被稱作個(gè)根的左子和右子所成。令bn表示n個(gè)點(diǎn)的二叉數(shù)，b0b11。特例溶有3個(gè)點(diǎn)的所有不一樣的二叉。一般情況:二叉有一個(gè)根點(diǎn)及n—1個(gè)非根點(diǎn)，后者又可分兩個(gè)子集，分構(gòu)成左子和右子。不失一般性，左子有k個(gè)點(diǎn)，右子有n—1—k個(gè)點(diǎn)。左子的所有可能的二叉的數(shù)量是bk,右子的所有可能的二叉的數(shù)量是bn1k（k=0,1，;n—1）。所以bn=b0A1b1bl2 bnJ0求解:令bn■BBvarmH-B-B-nHa即/1求解:令bn■BBvarmH-B-B-nHa即/1，得rrr+n1 1nr二rr_ n_1n1所以y=^，即bn=Cn1-rr一2n1rr2n2rrn1+r-rn11【例】有n個(gè)結(jié)點(diǎn)的所有不一樣的有序樹的個(gè)數(shù)是c（解）有序樹是本質(zhì)硬用中另一種重要的樹形結(jié)構(gòu)。當(dāng)一棵樹中任何一個(gè)結(jié)點(diǎn)的諸子樹的相對序次要考慮時(shí)，它就是有序樹。盡人皆知，任何一個(gè)有序樹都可用二叉樹表示。同時(shí)注意到，這棵二叉樹的根的右子樹是空二叉樹，故擁有n個(gè)結(jié)點(diǎn)的有序樹和擁有n—1個(gè)結(jié)點(diǎn)的二叉樹之間存在——對應(yīng)的關(guān)系。所以，有n個(gè)結(jié)點(diǎn)的有序樹的個(gè)數(shù)為bn1,即Cn。分別與有3個(gè)結(jié)點(diǎn)特例：4個(gè)結(jié)點(diǎn)的有序樹共有C4分別與有3個(gè)結(jié)點(diǎn)對應(yīng)規(guī)則：有序樹的長子樹作二叉樹的左子樹，次弟作右子樹?！纠坑蒼個(gè)1和n個(gè)0構(gòu)成的2n位的二進(jìn)制數(shù)，要求從左向右掃描，1的累計(jì)數(shù)不小于0的累計(jì)數(shù)，試求這樣的二進(jìn)制數(shù)有多少？（解）解法一：設(shè)知足條件的二進(jìn)制數(shù)有an個(gè)。將其視為由字符0和1構(gòu)成的二進(jìn)制串，現(xiàn)分類統(tǒng)計(jì)其個(gè)數(shù)以下：設(shè)從左向右掃描到第2k位時(shí)（1WkWn）,第一次出現(xiàn)了0的個(gè)數(shù)等于1的個(gè)數(shù)。那么在此以前，掃描就任何一位時(shí)，1的個(gè)

數(shù)是大于0的個(gè)數(shù)。比以下邊的二制串:111000n00(k=3),110100n00(k=3),1101010010(k4),1101010100(k=5)擁有種性的串有tk個(gè)，t=aakk1nk是因能夠?qū)⑶泻夏恳蟮拇智昂髢蓚€(gè)子串，前子串共2k位，后子串有2(n—k)位。第一，由目的條件知，后子串也是切合目要求的二制串，不過其度2(n—k)，故有ank個(gè)。其次，前子串，必其性知，當(dāng)去掉第1位和第2k位，剩下的2(k—1)位串也切合目條件，故前子串有ak1個(gè)。由乘法法，擁有此性的串共有ak1ank個(gè)。而相于不一樣的k(k=1,2,二口)，兩的二制串不行能相互有重復(fù)的狀況，故由加法法，所求的串的個(gè)數(shù)an=tan=t1t2tn=a0an1+a1an2an1a0且有a1=1。此外，察上式，可知-有a0=1。參按例3.4.9中對于數(shù)列｛bn｝所足的推關(guān)系的解法，可知11Cn1=n1c2nn++解法二:用擺列合的方法求解。本教材的配套料一《合數(shù)學(xué)學(xué)指》中對于第一章32的求解程?！?.5應(yīng)用【例】求以下隊(duì)列式dn的。

TOC\o"1-5"\h\z2100… 01210… 0dn=0121… 0i *0000 0 12（解）利用隊(duì)列式的性質(zhì)，將其按第一行睜開得2100 01210…d=012」.n■十TOC\o"1-5"\h\zfl ，22n0000 00 002 1 0 0 ■■■2 1 0 ■■■? 0 1 2 1 …0 0 0 0 01 1 0 0 …0 2 101?0 1 2 1 -■ V■■00000再將第二個(gè)n-1階隊(duì)列式按第一列睜開得2100 01210- 0dn=2dn1—0121…

ddn=2dn一1- n2dn_2dn1dn2二0故得定解 - -di=2,d2=3特色根x=1（二重），通解dn二A.Bn此中A、B隨意常數(shù)，代入初得所以即AB=2,A2B=所以即A二BJdn=n+1.【例】（排）n個(gè)有序元素的一個(gè)擺列，若每個(gè)元素都不在其本來在的地點(diǎn)，稱擺列位擺列，稱排。詳細(xì)地，如自然數(shù)1,2,…，n自己就是一個(gè)由小到大的有序擺列，在打亂序重排，要求數(shù)i不在第i個(gè)地點(diǎn)，就是位擺列。求所有位擺列的數(shù)量Dn，就是排。⑴n小的Dnn=1,1的排數(shù)D1=0.n=2,12的排21,排數(shù)D2=1.n=3,123的排：312和231,排數(shù)D3=2.兩個(gè)排能夠理解在自然擺列123中先將12排后得213，再在213中將3分與1或2互地點(diǎn)而得。n=4,排情況分三種（共兩）（1）4321,3412,2143:4分與1,2,3中某一個(gè)互地點(diǎn)，其他兩元素排；（2.1）4123,3421,3142:4與123的一個(gè)排312構(gòu)成3124，再將4分與各數(shù)互；（2.2）4312,2413,2341:123的排231,方法同（2.1）。

(2)一般律由此能夠看出生排的一種方法：n個(gè)數(shù)1?n的自然序擺列12f，任取此中一數(shù)i(1<i<n)，將所有排分兩：1)i與其他某數(shù)互地點(diǎn)后，其他的n—2個(gè)數(shù)排，共得(n1)Dn_2個(gè)排；2)i在原地點(diǎn)不，其他n—1個(gè)數(shù)先排，而后i再與此中每一個(gè)數(shù)互地點(diǎn)可得(n—1)DnU個(gè)排。(3)Dn的推關(guān)系fDn=(n/QnL+Dn_).2反推可知，D0 D1=0,D2=1一。1(4(4)Dn的不一樣表示能夠明Dn與足推關(guān)系數(shù)列C］是同一數(shù)列。即Tn=nTn1.-1n,n2的T「0T1=D =T1=D =0,T2=TT.

k

k1k

(5)求解1十)1Tk-12=1十)

k1Dk1二D2-1k1解之得(；例)n(_1)kD=n!' n k!kF當(dāng)n充足大，可得Dn的特別的近似公式n!—(n>>1)且eDn_n!<e是因n!二n!二(1)k(1)kn-n!% k!kF

一nh一k!k-0n!0c-Ik看（」）kn!1k!1[[(n+1)!(n+2)!二l(n+3)!(n4)!(n5)!(n6)!n+2 (n+1加+2Jn+4)n1n2:n3n4n61 1 1 1 ■ ■ ■ <22 23 252722411226122411226一十一十—4 .22224 21_1_12451=一+ =<4312-2\n為偶.D 0數(shù)一 Dn 工n為奇e0數(shù)wordn!en為奇數(shù)In為奇數(shù)il-e"【例】(經(jīng)濟(jì)模型)由諾貝爾獎(jiǎng)獲取者PaulSamuelson于1939年提出。an 第n年公民總收入，g(n) 政府支出，cn個(gè)人花費(fèi)支出，pn——個(gè)人的投資。an=gnHCn+Pn，叱0基本假定：Cn與an」成正比，即Cn=二an1,n0,0二二：1依據(jù)經(jīng)濟(jì)學(xué)的說法，常數(shù)a稱為花費(fèi)的臨界偏向。再設(shè)Pn=P(cn—cn」),n31式中B是非負(fù)常數(shù)，稱為加快系數(shù)。所以p二二二a -a:=二i：a-a_進(jìn)而對全部nn22，有1 n n1n2an=g(n)+Cn+Pn=gn)+- “a” ￡=g出戶9+P)n1一避nT即: ：-■a十：'a二 _【例】某粒子反響器內(nèi)有高能自由粒子，低能自由粒子和核子3種，假定一個(gè)高能粒子撞擊一個(gè)核子且被汲取惹起它放射出3個(gè)高能粒子和一個(gè)低能粒子，一個(gè)低能粒子撞擊核子且被汲取并惹起它放出兩個(gè)高能粒子和一個(gè)低能粒子。設(shè)開始n=0奇妙時(shí)，在擁有核子的系統(tǒng)里放入一個(gè)高能粒子，問第n奇妙時(shí)系統(tǒng)中高能、低能粒子各有多少？（解）設(shè)第n奇妙時(shí)，系統(tǒng)里有高能自由粒子an個(gè)，低能自由粒子b自由粒子bn個(gè)由條件知a0=1,b0=0并有遞推關(guān)系an1ban1b二3an-2bn解之得3 _—(23 _—(2,3)n363b二—(2-3)n6_3 _二^(2-,3)n36—(2_、3)nII6【例】核反響堆中有，兩種粒子，每單位時(shí)間，一個(gè)粒子分裂為3個(gè)粒子，1【例】核反響堆中有，兩種粒子，每單位時(shí)間，一個(gè)粒子分裂為3個(gè)粒子，1個(gè)工粒子分裂為：2個(gè)粒子和一個(gè)粒子，假定t=0時(shí)辰，反響堆中只有1個(gè)粒子，那么，在t=100時(shí)辰，該反響堆中、粒子各有多少，總數(shù)為什么？（解）設(shè)t=n時(shí)辰，粒子有an個(gè)，題意可得定解問題ran=bn3jbn=3an_J2b1r1a0=1,b0=0由上可得粒子有bn個(gè)，由an=bn—13an -2 +2bn -2 =3an -2 +2an -1XI.乙 XI.乙 XI.乙 XI.Lb0=a1=0,于是，｛an｝的定解問題為二2a口一二2a口一13an2a0=1,a1=0用特色根法解之得

an」3n.—34 4進(jìn)而ba_13n1 3（1）ni+nn1 4 4所以在第n刻反堆的粒子數(shù)anbn二3n那么，在第100刻堆內(nèi)的粒子數(shù)是3100。另法:就堆內(nèi)粒子數(shù)而言，因?yàn)閍粒子和B粒子都是分解3個(gè)粒子，故t=1亥刻共有3個(gè)粒子（3個(gè)B），t=2刻共有3義3=32個(gè)粒子（3X2個(gè)b個(gè)粒子，3個(gè)a粒子），……，到t=n刻,3n個(gè)粒子。【例】（信號）在信道上a,b,c構(gòu)成的字符串（度n），兩個(gè)a相的串不可以，求允的串的個(gè)數(shù)。（解）用an表示信道允的度n的串的個(gè)數(shù)，然，a1=3,a2a2=328，當(dāng)n>3，將切合要求的串分兩：第一：第一字母不是a的串有2an1個(gè)；第二：首字母a，次字母必b或c,的串有2an_2個(gè)。合以上狀況有an-2'an-1 n2ta「3,a2=8近似的問題:兩個(gè)0不可以相的三制串的個(gè)數(shù)一般情況：兩個(gè)0不可以相的p制串的個(gè)數(shù)an,有an=P-1an1naa1二p,a2=p2_1【例】一個(gè)圓形地區(qū)分紅n個(gè)扇形地區(qū)，用k種顏色涂這些扇形，使相鄰的扇形沒有相同的顏色，問共有多少種染法？(解)令an表示n個(gè)扇形的所有知足條件的染法數(shù)量，R1,R2,,Rn表示這n個(gè)扇形，扇形Rn的涂色方法，至多有兩種狀況：第一種狀況：Rn1和Ri同色，這時(shí)Rn有k-1種顏色可供選擇，并且扇形R1至Rn-2有an-2種涂色方法，所以共有(k-1)an-2種染法。第二種狀況：Rn_1和R1異色，這時(shí)Rn有n-2種顏色可供選擇，并且扇形R1至Rn1有an1種涂色方法。所以共有(k-2)an1種染法，故知涂色方法總數(shù)的遞推方程為：ank1an2k2an1；a2二(kk1,-a+3<k^1k-2[=(_) =(一X-解之得ank1n1nk1解之得=(-)+(-)(-)

【例】平面上有n個(gè)圓(n>2)，任何兩個(gè)圓都訂交但無3個(gè)圓共點(diǎn)，問這n個(gè)圓把平面區(qū)分紅多少個(gè)不連通的地區(qū)？(解)設(shè)這n個(gè)圓把平面區(qū)分紅an個(gè)不連通的地區(qū)。初值：a0=1,a1=2,a2=4。剖析：當(dāng)n>2時(shí)，n-1個(gè)圓把平面區(qū)分紅an1個(gè)不連通的地區(qū)。新加入的圓C與其他n-1個(gè)圓都訂交，且所得的2(n-1)個(gè)交點(diǎn)相互相異(因無3個(gè)圓共點(diǎn))，這2(n-1)個(gè)交點(diǎn)把圓C分紅2(n-1)段弧，每段弧把本來的一個(gè)地區(qū)區(qū)分紅兩個(gè)小地區(qū)，故增添了2(n-1)個(gè)地區(qū)，進(jìn)而an知足遞推關(guān)系

jan=n+ 2n-1ai=2解之得 an=n2-n2上式仍成立。n2_n2,nJ1，口二0【例】【例】(排序算法)應(yīng)用:據(jù)，在算機(jī)的所有運(yùn)轉(zhuǎn)里，幾乎有1/4是用在排序上。排序問題：定n個(gè)數(shù)ai,ai寄存于在元K(i)(i=1,2，…，n)，要求按增序次其從頭擺列。【算法一】直接排序：基本思路:第一步從n個(gè)數(shù)中出最大者，將它與K(n)中的數(shù)交地點(diǎn)(此K(n)寄存的是最大的數(shù))；第二步，余下的n-1個(gè)數(shù)，地重復(fù)行上述做法，出此中最大者，與K(n-1)中的數(shù)交「一。n-1步后，就達(dá)到了排序目的。例4672513—4632517復(fù)雜性：僅用元素的比較次數(shù)來計(jì)算它的時(shí)間復(fù)雜性。時(shí)間復(fù)雜度：令T(n)表示用直接選擇排序法將n個(gè)元素排序所需的比較次數(shù)。那么，第一步在n個(gè)數(shù)中找最大者，需要比較n-1次。算法履行一步后，對余下個(gè)n-1個(gè)元素再排序需要TnL次比較。由加法法例T(n)=T(n_1)(n1),n_2T(1)=0n解之得 T(n)= -=2(n1) O(n2)【算法二】分治歸并排序：本算法是分治策略在排序問題上的應(yīng)用?；舅枷耄喊汛判虻臄?shù)列a1，a2一an(設(shè)n=2m)區(qū)分成大小相同的兩個(gè)子序列a,a,,a 和a,a,,aaH■ IBB2n n1.「_n2“n2 2分別對每個(gè)子序列中的數(shù)按遞加序次進(jìn)行排序，而后再把這兩個(gè)排好序的子序列歸并成一個(gè)遞加數(shù)列，算法是遞歸進(jìn)行的。當(dāng)對兩個(gè)已排好序的子序列進(jìn)行歸并時(shí)，把每個(gè)