§6.2常系數(shù)線性齊次遞推關(guān)系《組合數(shù)學(xué)引論》

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

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