组合数学期中论文

常系数递归数列的简单推广及其应用摘要：本文利用k阶级线性差分方程及常系数非齐次微分方程特解的设解规律对k阶常系数线性递归数列进行简单推广到了k阶常系数非齐次线性递归数列，并进行了多类型的设解及其应用总结，又引进矩阵理论增加了k阶线性递归数列通项公式的求法，拓宽其应用范围。关键词：递归数列；差分方程；设解；矩阵本学期，在吴克俭老师的指导下我们进行了组合数学课程的学习探究，主要的内容包括了排列与组合，二项式系数，调和数Fibonacci数和Catalan数，第二类Stirling数和Bell数，第一类Stirling数，正整数的分拆，Bernoulli数与Euler数，递归数列，形式幂级数等知识内容，而在本文当中，我选取了吴老师课堂上没有深入探讨的关于递归数列的部分知识内容进行了简单的推广与应用，即有对常系数递归数列进行简单的推广及其应用。第一部分：递归数列的知识回顾：1、递归关系2、齐次常系数线性递归关系：1）k阶常系数齐次线性递归关系2）k阶齐次线性递归关系3、其他递归关系：1）非齐次常系数线性递归关系2）卷积型递归关系3）双下标递归关系第二部分：推广与应用一、对于常系数齐次线性递归关系的简单推广，即k阶常系数非齐次线性递归关系。为了方便，我们可以设k阶常系数非齐次线性递归数列的一般形式为)0(),(0110pnfapapapnkknkn（1）其中)(nf，(n=O，1，2，...)是一给定的数列，kppp,,,10是给定的常数。显然，我们可以得到与(1)所对应的k阶常系数齐次线性递归数列是)0(,00110papapapnkknkn（2）由吴老师课堂笔记中3、其他递归数列关系1）非齐次常系数线性递归关系的部分内容可以了解到，(1)的通解等于(2)的通解加上(1)的一个特解。而对于常系数齐次线性递归数列(2)的通解，我们可以用定理8.1至定理8.4中的特征方程与特征根及待定系数的方法进行解答从而求出（2）的通解，或者通过母函数、矩阵等方法也求出，不管怎样，求(1)的通解关键就在于求出(1)的一个特解。若仅仅局限于特征方程与特征根及待定系数法是不能对一般的常系数非齐次线性递归数列进行求解的，只有当)(nf是具有某些特殊形式的函数时，例如：①)(nf是n的t次多项式时，此时1便是常系数齐次线性递归数列（2）的l重特征根)0(l，那么（1）的特解可以通过待定系数的方法求出。②)(nf=na时，a便是常系数齐次线性递归数列（2）的l重特征根)0(l，那么（1）的特解可以通过待定系数法求出。然而，在一般情况下，若没有上述的特殊条件，我们在进行常系数非齐次线性递归数列的就显得有点困难，那么下面利用差分的概念将(1)转化为常系数非齐次线性差分方程，从而得到(1)的特解。首先，对于数列nnaa可看成是定义在非负整数集上的函数，而其与整数0n之值便是na，差分算子是一个在这些函数组成集合上的变换，定义其为nnnaaa1；高阶差分算子k，(k=2，3，....)，定义其为)(1nknkaa，同时我们规定I0，记I是恒等算子，即有nnaIa，(n=0，1，2，...)。其次，与差分算子有密切关系的是位移算子E，定义其为1nnaEa；高阶位移算子kE，(k=2，3，...)；定义其为knnknkaaEEaE)(1，并规定IE0。显然可得，IE，从而有kkkkkkkCCCIE10)(。利用位移算子，(1)可记为)()(1110nfaIcEcEcEcnkkkk（3）其中nnf)(是一给定的数列，kkcccc,,,,110是给定的常数，如果有k个相连的值为给出，成为边界条件，此时（3）将有唯一的解。然而，由位移算子与差分算子的关系，(3)又可以进一步化为)()'''(110nfaIcccnkkk（4）其中kkcccc',',,','110是已知常数。这样(1)就转化为常系数非齐次线性差分方程(4)。对（4）两边去l次差分，得)()''''(21110nfaccccnkkkk)()''''(22311120nfaccccnkkkk............)()'''(1112110nfaccclnlklklk)()''''(11110nfacccclnlklklklk若)(nfl是一个与n无关的常量，不妨设Mnfl)(，则最后一个方程显然有解knlcMa'，此时011nlknlknlaaa。将011nlknlknlaaa，knlcMa'代入倒数第二个方程可求得nla1。依次往上推，一直到(4)即可求得(1)的一个特解na。通过上述利用k阶线性差分方程的方法进行常系数齐次线性递归数列的推广过程，我们可以清楚地明白到，对于求(1)的特解，关键在于求差分方程(4)的特解。易得(4)的特解可求，而其最简单的情形就是当将令)(nfl成为一个与n无关的常量。二、对于利用差分方程进行对常系数非齐次线性递归数列进行求通解的方法的常见应用类型。由（一）中的推广过程中，我们若想保证)(nfl是一个与n无关的常量，那么常见的方式就是使得f(n)成为n次多项式)(nPm或指数函数anmenP)(或余弦线性函数nenPanmcos)(或正弦线性函数nenPanmsin)(或几个简单函数之和中一种情况。又根据常系数非齐次线性方程的特解的设解规律，即“是什么设什么，含于Y乘于x”的规律，指的是“f(n)是什么函数，方程的特解就设成什么函数；如果上面所设的特解含于对应的齐次方程的通解Y(即所设特解可以完全或部分地与对应的齐次方程的通解合并)，则用x乘以前面所设的特解，作为新设特解；若仍含于对应的齐次方程的通解，再乘以x，直到不含于对应的齐次方程的通解Y为止。”我们可以知道，常系数非齐次线性微分方程的特解的规律，即可以引申到常系数非齐次线性递归数列中去。为了方便论证，我们将取二阶常系数非齐次线性递归数列为例。首先，我们设定二阶常系数非齐次线性递归数列为)0(),(021120pnfapapapnnn（5）由1.1的推导过程，我们可以很快得出对应于(5)的差分方程为)()(2120nfaIpEpEpn或)()(2120nfaIqqqn（6）其中210210100,2,pppqppqpq①)()(nPnfk，当)(nf为n次多项式时，其特解应为n次多项式。设kkknanaanp10)(是n的k次多项式。由于)(npk求k次差分后成为常数，所以对（6）两边取k次差分后可求得）常量（0!22qqkaaknk②)()(nPenfkan，当)(nf为指数函数时，其特解应为同类指数函数。此时，作通项变换nannbea，代入（5）得)(211202nPbpbpebpeknnana进一步化为)()(2120nPbIqqqkn（7）其中，21,,qqqo仍是常数。（7）式已具有①的形式，故可求出数列nb的一个特解*nb，从而由nannbea可得数列na的一个特解**nannbea。③nnPenfkancos)()(或nnPenfkansin)()(，当)(nf为正、余弦的线性函数，其特解应为设为同类正、余弦的线性函数。构造新的差分方程)(),()()()(2120inPenPkeaIqqqknnin（8）此时（8）具有②的形式，因此可求出数列na的一个特解*na又Re*na是差分方程nnPeaIqqqkanncos)()(2120的特解。Im*na是差分方程nnPeaIqqqkannsin)()(2120的特解。④)()()(21nfnfnf，当)(nf为几个简单函数之和，其特解应为同类型简单函数之和。其中)sin)((cos)()(),()(211nnPennPenfnQenfkankann或，)(),(1nPnQk分别是n的l次和k次多项式。由)()()(2121120nfnfnfapapapnnn(9)可得两个常系数非齐次线性递归数列)(121120nfapapapnnn（10）)(221120nfapapapnnn（11）根据线性递归数列解的叠加原理知（9）的特解等于（10）与（11）的特解之和。而（10）具有②的形式，（11）具有③的形式。从而（9）的特解可求。从以上讨论可见，通过对)(nf特解的设解规律“是什么设什么，含于Y乘于x”的规律引申到特解的求解规律，验证了我们前期的求解思路，则通过差分方程的求解方法得到我们所求常系数非齐次线性递归数列需要的特解。三、对k阶齐次线性递归数列的简单推广，即利用矩阵判断k阶齐次线性递归数列其敛散性，并求出其通项公式。1）k阶齐次递归数列敛散性的判断设k阶齐次递归数列nf的递推公式为nknkknknknfafafafaf112211，（1）其中n=1,2,...,令,01000001,12111kkkknknknknaaaaAfffM则knknknMAAMM1。（2）由(2)式易得定理1nf收敛knnMlim存在nnAlim存在.若021kfff则0nf.下设kfff,,,21不全为零.定理2(1)设矩阵A有k个不同的特征根,,,,21k则nnflim存在当且仅当;,,2,1,1kii（2）若矩阵A的特征根有重根i，则nnflim存在当且仅当1i.证（1）若矩阵的k个不同的特征根,,,,21k则存在可逆矩阵T（T的第i列恰是A的对应于i的特征向量）使得,,121121knknnknknkMTTMAaMTTA所以nnflim存在knnflim存在nnAlim存在ninlim存在;,,2,1,1kii（2）若矩阵A的全部特征根为,,,,21且,21kkkk则,121knnnknMTJJJTM其中jjjjJ111是jjkk级若当块.因,111111njnjnknjknnjnnjnjCCCJjj0limnknan（k为大于1的自然数），于是nnflim存在knnMlim存在nnAlim存在1j，j是重根.2）递归数列通项式的求法由矩阵A的表达式算出A的特征多项式,)(111kkkkaaaAEf求出上述定理2证明中的可逆矩阵T，即得nA的关于n的表达式，从而得出nf的通项公式。参考文献：[1]邓勇.常系数非齐次线性递归数列求特解的简易方法.达县师范高等专科学校学报.2006(9）：25-26.[2]喻德生王敏.浅谈常系数非齐次线性方程特解的设解规律与教学.高等数学研究.2004(5):41-44.[3]周立仁.k阶线性递归数列的通项公式的矩阵求法.湖南理工学院院报（自然科学报）.2011(9):24-25.[4]夏宗汇.生成函数与差分方程.数学传媒第二卷第四期.