資源描述：
《k階線性遞推數(shù)列_20110410》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。
1、k階線性遞推數(shù)列Tanzxproudly20110410目錄k階線性遞推數(shù)列1準(zhǔn)備2問題引入3通項公式推導(dǎo)：無重根情況3有重根的情況6總結(jié)7附錄：函數(shù)S——遺留的證明8準(zhǔn)備?為了研究以下問題，先考慮一個一元k次方程，它一定可以寫成以下形式：x-x1x-x2x-x3…x-xk=0。?考慮它的展開形式：x-x1x-x2x-x3…x-xk=i=1kx-xi=xk-0S0+xk-1S1+xk-2S2+…+xk-kSk*Si代表系數(shù)=xk-0Sk,0+xk-1Sk,1+xk-2Sk,2+…+xk-kSk,k*在
2、這里定義：函數(shù)Sk,i為一個一元k次方程展開式的k-i次項的系數(shù)。*特別地，規(guī)定：對于任意k，都有Sk,0=1。*這個定義是抽象的，對于函數(shù)Sk,i的具體表達(dá)式，見附錄。=i=0kxk-iSk,i;?下面考慮這個展開式的一個遞推特性：i=0kxk-iSk,i=x-x1x-x2x-x3…x-xk=x-x1x-x2x-x3…x-xk-1x-xk=i=0k-1xk-1-iSk-1,ix-xk=xi=0k-1xk-1-iSk-1,i-xki=0k-1xk-1-iSk-1,i=i=0k-1x1+k-1-iSk-
3、1,i-xki=0k-1xk-1-iSk-1,i。*以上是前提準(zhǔn)備。問題引入?一個k階線性遞推數(shù)列是指符合以下遞推式的數(shù)列：ak-0+nS0+ak-1+nS1+ak-2+nS2+…+ak-k+nSk=0;其中a0,a1,a2,…,ak-1已知。?將其轉(zhuǎn)化為與一元k次方程類似的形式：ak-0+nS0+ak-1+nS1+ak-2+nS2+…+ak-k+nSk=ak-0+nSk,0+ak-1+nSk,1+ak-2+nSk,2+…+ak-k+nSk,k*轉(zhuǎn)化關(guān)系：xk-i?ak-i+n*鑒于這個一元k次方程與
4、數(shù)列遞推式的關(guān)系，所以稱這個方程為這個數(shù)列的特征方程。=i=0kak-i+nSk,i=i=0k-1ak-i+n+1Sk-1,i-xki=0k-1ak-i+nSk-1,i*這里使用了與上面對方程展開式相同的變化方式；*這個結(jié)論并不是顯然的，這里只是類比解釋而已，具體證明方法請看附錄。?為表述方便，規(guī)定Akn=i=0kak-i+nSk,i，那么就有：Akn=Ak-1n+1-xkAk-1n;而一個k階線性遞推數(shù)列就是指符合Akn=0的數(shù)列。通項公式推導(dǎo)：無重根情況?下面推導(dǎo)k階線性遞推數(shù)列的通項公式。Akn
5、=0;Ak-1n+1-xkAk-1n=0;Ak-1n+1=xkAk-1n;Ak-1n=xknAk-10;*為了表示方便，以下規(guī)定：Ck-1k=Ak-10，取“對于Ak-1n的xkn項的系數(shù)”之意;*Ck-1k是與n無關(guān)的系數(shù)。Ak-1n=xknCk-1k;*這里使用了等比數(shù)列的通項公式；*等比數(shù)列的通項公式可以很簡單地通過數(shù)學(xué)歸納法得到。Ak-2n+1-xk-1Ak-2n=xknCk-1k;Ak-2n+1-xk-1Ak-2n=xknCk-1kxk-xk-1xk-xk-1;Ak-2n+1-xk-1Ak-
6、2n=xkxknCk-1kxk-xk-1-xk-1xknCk-1kxk-xk-1;Ak-2n+1-xkn+1Ck-1kxk-xk-1-xk-1Ak-2n-xknCk-1kxk-xk-1=0;*這樣就把xknCk-1k分配到了左邊的兩項里；*可以發(fā)現(xiàn)，該方法成立的前提是xk-xk-1≠0。Ak-2n+1-xkn+1Ck-1kxk-xk-1=xk-1Ak-2n-xknCk-1kxk-xk-1;Ak-2n-xknCk-1kxk-xk-1=xk-1nAk-20-xk0Ck-1kxk-xk-1;Ak-2n=xk
7、nCk-1kxk-xk-1+xk-1nAk-20-xk0Ck-1kxk-xk-1;*規(guī)定：Ck-2k=Ck-1kxk-xk-1，Ck-2k-1=Ak-20-xk0Ck-1kxk-xk-1;于是有：Ak-2n=xknCk-2k+xk-1nCk-2k-1;?*規(guī)定：Ck-m+1k-j=Ck-mk-jxk-j-xk-m其中j=0,1,2,…,m-1，Ck-m+1k-m=Ak-m+10-j=0m-1xk-j0Ck-mk-jxk-j-xk-m。?接下來證明命題：對于任意m=1,2,…,k，都有：Ak-mn=xk
8、nCk-mk+xk-1nCk-mk-1+xk-2nCk-mk-2+…+xk-m-1nCk-mk-m-1即：Ak-mn=j=0m-1xk-jnCk-mk-j證明：首先，對m=1的情況已經(jīng)進行過闡述，是成立的；然后假設(shè)：Ak-in=xknCk-ik+xk-1nCk-ik-1+xk-2nCk-ik-2+…+xk-i-1nCk-ik-i-1;即：Ak-in=j=0i-1xk-jnCk-ik-j;那么：Ak-i+1n+1-xk-iAk-i+1n=j=0i-1xk-
