资源描述：
《k阶线性递推数列_20110410》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、k阶线性递推数列Tanzxproudly20110410目录k阶线性递推数列1准备2问题引入3通项公式推导：无重根情况3有重根的情况6总结7附录：函数S——遗留的证明8准备≫为了研究以下问题，先考虑一个一元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代表系数=xk-0Sk,0+xk-1Sk,1+xk-2Sk,2+…+xk-kSk,k*在
2、这里定义：函数Sk,i为一个一元k次方程展开式的k-i次项的系数。*特别地，规定：对于任意k，都有Sk,0=1。*这个定义是抽象的，对于函数Sk,i的具体表达式，见附录。=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。*以上是前提准备。问题引入≫一个k阶线性递推数列是指符合以下递推式的数列：ak-0+nS0+ak-1+nS1+ak-2+nS2+…+ak-k+nSk=0;其中a0,a1,a2,…,ak-1已知。≫将其转化为与一元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*转化关系：xk-i↔ak-i+n*鉴于这个一元k次方程与
4、数列递推式的关系，所以称这个方程为这个数列的特征方程。=i=0kak-i+nSk,i=i=0k-1ak-i+n+1Sk-1,i-xki=0k-1ak-i+nSk-1,i*这里使用了与上面对方程展开式相同的变化方式；*这个结论并不是显然的，这里只是类比解释而已，具体证明方法请看附录。≫为表述方便，规定Akn=i=0kak-i+nSk,i，那么就有：Akn=Ak-1n+1-xkAk-1n;而一个k阶线性递推数列就是指符合Akn=0的数列。通项公式推导：无重根情况≫下面推导k阶线性递推数列的通项公式。Akn
5、=0;Ak-1n+1-xkAk-1n=0;Ak-1n+1=xkAk-1n;Ak-1n=xknAk-10;*为了表示方便，以下规定：Ck-1k=Ak-10，取“对于Ak-1n的xkn项的系数”之意;*Ck-1k是与n无关的系数。Ak-1n=xknCk-1k;*这里使用了等比数列的通项公式；*等比数列的通项公式可以很简单地通过数学归纳法得到。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分配到了左边的两项里；*可以发现，该方法成立的前提是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;*规定：Ck-2k=Ck-1kxk-xk-1，Ck-2k-1=Ak-20-xk0Ck-1kxk-xk-1;于是有：Ak-2n=xknCk-2k+xk-1nCk-2k-1;≫*规定：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的情况已经进行过阐述，是成立的；然后假设：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-
