§6.2常系數線性齊次遞推關系《組合數學引論》

－Chapter6一、定義定義1(f(n)}為一數列,C1,C2,…,Ck為k個常數,且Ck≠0,則稱遞推關系：為k階常系數線性齊次遞推關系.若數列{bn}滿足遞推關系,即則稱這個數列{bn}為遞推關系的解．若{bn}還滿足初始條件，則稱{bn}為滿足初始條件的特解，顯然滿足初始條件的特解是唯一的．(1)定義2方程稱為遞推關系(1)的特征方程，它的根稱為遞推關系的特征根．(1)由于Ck≠0，所以特征根為非零根．二、解的性質性質1．設q是非零復數,f(n)=qn為遞推關系(1)的解的充要條件為q是遞推關系(1)的一個特征根．證明設f(n)=qn為遞推關系的解，即由于，所以

即q為遞推關系的一個特征根．反之結論也成立．性質2．如果h1(n),h2(n)為遞推關系(1)的兩個解，則Ah1(n)+Bh2(n)也是遞推關系(1)的解,其中A、B為任意常數．證明設Tn=Ah1(n)+Bh2(n),由于h1(n),h2(n)為遞推關系的解，有，所以Ah1(n)+Bh2(n)為遞推關系的解．這是解的線性疊加性質,可推廣到m個解的情況.(1)三、遞推關系的通解定義2設h1(n),h2(n),…,hk(n)為遞推關系(1)的k個解,若對(1)的任一個解h(n),都可適當選擇常數使得則稱為遞推關系(1)的通解,其中b1,b2,…,bk為任意常數．定理4.2.1若為遞推關系(1)的k個互不相等的特征根,則為遞推關系(1)的通解,其中為任意常數．證明顯然為遞推關系(1)的解.(1)設h(n)是遞推關系(1)的任一個解,它由k個初值h(0)=a0,h(1)=a1,……,h(k-1)=ak-1唯一確定.因為方程組的系數行列式(Vandermonde行列式)不為零,所以方程組有唯一解即有結論成立.下面研究當特征根有重根時，遞推關系的通解．引理1.若q為k階常系數線性齊次遞推關系(1)的二重特征根，則為遞推關系的解．證明令因為q為P(x)的二重根，所以q也為Pn(x)的二重根，從而q為的一重根，也為的一重根．又由于即為遞推關系(1)的解．由引理1易證得下面的引理2.(1)引理2.若q為k階常系數線性齊次遞推關系（1）的m重特征根則為遞推關系的解．定理2是遞推關系(1)的全部不同特征根，其重數分別為,則遞推關系的通解為其中．例1求解遞推關系解它的特征方程為：特征根為:所以遞推關系的通解為代入初值得方程組解方程組得所以遞推關系的解為：例2求解遞推關系解遞推關系的特征方程為：特征根為:所以遞推關系的通解為代入初值得方程組：解方程組得：,所以遞推關系的解為：例3核反應堆中有和兩種粒子，每秒鐘內一個粒子可反應產生三個粒子，而一個粒子又可反應產生一個粒子和兩個粒子.若在時刻t=0時反應堆中只有一個粒子,問t=100秒時反應堆將有多少個粒子?多少個粒子?共有多少個粒子?解設在t時刻的粒子數為f(t),粒子數為g(t)，依題意的下面遞推關系它的特征方程為：特征根為:所以遞推關系的通解為代人初值有解方程組，得所以遞推關系的解為從而有因此，例4求解遞推關系解遞推關系的特征方程為：特征根為:所以遞推關系的通解為代入初值得方程組：