线性常系数非齐次递推关系

组合数学讲义3章递推关系递推关系§3.1 基本概念（一）递推关系定义3.1.1 （隐式）对数列aii 0 和任意自然数n，一个关系到an和某些个ai i n 的方程式，称为递推关系，记作F a0,a1, ,an 0 (3.1.1)__例an an 1 an 2 a0 n 0an 3an 1 2an 2 2a1 1 0定义3.1.1＇（显式）对数列aii 0 ，把an与其之前若干项联系起来的等式对所有n≥k均成立（k为某个给定的自然数），称该等式为ai 的递推关系，记为an F an 1,an 2, ,an k (3.1.1)＇例an 3an 1 2an 2 2a1 1 （二）分类（1）按常量部分：① 齐次递推关系：指常量＝0，如Fn Fn 1 Fn 2；② 非齐次递推关系，即常量≠0，如hn 2hn 1 1。

（2）按ai的运算关系：组合数学讲义① 线性关系，F是关于ai的线性函数，如（1）中的Fn与hn均是如此；② 非线性关系，F是ai的非线性函数，如hn h1hn 1 h2hn2 hn 1h1。

（3）按ai的系数：① 常系数递推关系，如（1）中的Fn与hn；② 变系数递推关系，如pn npn 1，pn 1之前的系数是随着n而变的。

（4）按数列的多少：① 一元递推关系，其中的方程只涉及一个数列，如(3.1.1)和(3.1.1)＇均为一元的；② 多元递推关系，方程中涉及多个数列，如an 7an 1 bn 1bn 7bn 1 an 1（5）显式与隐式：yn 1（三）定解问题xn 1yn h yn 1 2 yn 1定义3.1.2 （定解问题）称含有初始条件的递推关系为定解问题，其一般形式为F a0,a1, ,an 0,(3.1.2)a0 d0,a1 d1, ,ak 1 dk 1所谓解递推关系，就是指根据式(3.1.1)或(3.1.2)求an的与a0、a1、、an－1无关的解析表达式或数列{an}的母函数。

用升阶法求常系数非齐次线性递推关系的特解黄纯洁【摘要】This article makes use of the sequence difference, and transforms the invariable coefficient number of times different linear recursion sequence to the coefficient inhomogeneous linear difference equation （ qo （qo△k＋i＋q1△k＋i-1…＋qk△i）an=△if（n）, The fourf（n）=gm （n）,f（n）=qngm（n）,f（n）=qngm（n）cosβn,f（n）=qkgm（n）sinβn） are discussed under constant coefficient inho-mogeneous linear difference equation, thus obtains the special solutions of coefficient inhomogeneous linear recursion sequence, which is called the method of increasing order.%利用数列的差分算子和移位算子，将常系数非齐次线性递推关系转化成为常系数非齐次线性差分方程（qo△k＋i＋q1△k＋i-1…＋qk△i）an=△if （n），并将f（n）=gm（n），f（n）=qngm（n），f（n）=qngm（n）cosβn，f（n）=qkgm（n）sinβn）这四种类型的常系数非齐次递推关系转化为相应的差分方程，从而得到求常系数非齐次线性递推关系特解的简易方法——升阶法。

【期刊名称】《广东石油化工学院学报》【年(卷),期】2011(021)006【总页数】4页(P67-69,74)【关键词】差分方程;差分算子;移位算子;特解【作者】黄纯洁【作者单位】华南师范大学数学科学学院,广东广州510631【正文语种】中文【中图分类】O175.70 引言设k阶常系数非齐次线性递推关系形式为p0an+k+p1an+k-1+…+pkan=f(n)(p0,pk≠0),(1)。

关于常系数非齐次线性递推关系特解的注记唐善刚【摘要】By using algebraic properties of one-variable polynomial multiple root and block matrix method of solving non-homogeneous linear equations,it is proved that a class of constant coefficient non-homogeneous linear recurrence relation only depends on the computational formula of constant coefficient's particular solution and its proof.These results expand the corresponding ones in the existing literatures.Two examples for the application of particular solution of constant coefficient non-homogeneous linear recurrence relation are given in the final part for the purpose of proving the validity of particular solution of constant coefficient non-homogeneous linear recurrence relation.%利用一元多项式重根的代数性质与求解非齐次线性方程组的分块矩阵方法给出常系数非齐次线性递推关系的一类只依赖于常系数的特解计算公式及其证明,所得结果拓宽了已有文献的相应结果,最后,给出两个实例作为常系数非齐次线性递推关系的特解计算公式的应用,验证了特解计算公式的有效性.【期刊名称】《西华师范大学学报（自然科学版）》【年(卷),期】2017(038)001【总页数】6页(P75-79,105)【关键词】导数;一元多项式;重根;常系数非齐次线性递推关系;特解【作者】唐善刚【作者单位】西华师范大学数学与信息学院,四川南充 637009【正文语种】中文【中图分类】O157.1求递推关系的显式解是组合学的一个重要研究课题，关于常系数线性齐次递推关系的显式解可以应用生成函数［1-5］给出统一的求解，但用生成函数试图求得常系数非齐次线性递推关系的显式解往往需要很高的技巧，而应用代数方法［6-7］及赋权有向图路径的权和［8］得到的常系数线性齐次及非齐次递推关系的显式解是一个多重求和公式，由于该多重求和公式中的求和变量依赖于某个线性不定方程的所有非负整数解，进而导致显式解的多重求和公式在应用中的诸多不便。

常系数线性非齐次递归关系的特解廖毛黄宇晨索朗多吉常系数线性非齐次递归关系：()()()导出递归关系）称为其（其中性非齐次递归关系阶常系数线系叫做的函数，则这个递归关是关于是常数，其中：换一种表达形式归关系：是一个数列，且满足递0,0,,,r 2211r r 21r 2211r 2211=++++≠=++++++++=---------r n n n n r n n n n r n n n n n a c a c a c a r n n f c c c c n f a c a c a c a n f a c a c a c a a求解非齐次常系数线性递归关系的通解可以分为三个步骤：1.求出非齐次常系数线性递归关系的一个特解；2.求解非齐次常系数线性递归关系的导出递归关系的通解；3.非齐次常系数线性递归关系的通解等于前两个解之和。

故求解非齐次常系数线性递归关系的通解可以转化成求解非齐次常系数线性递归关系的导出递归关系的通解和非齐次常系数线性递归关系的一个特解。

齐次常系数线性递归关系的通解有求解公式，故求解非齐次常系数线性递归关系的通解的关键在于求其特解。

在我们的学习中，一般只讨论常系数齐次线性递推关系通解的求法，很少涉及常系数非齐次线性递推关系通解的求法，即使有也只是介绍了它的通解的结构（即非齐次线性递推关系的通解等于它的一个特解与它所对应的齐次线性递推关系的通解之和）而其特解为什么是这样的形式，是怎样推导出来的均没有给出理论上的证明，下面我给出了常系数非齐次线性递推关系关于特殊函数特解的统一求法。

()()()()()()()()()()0q c ,0q c 0q c 0q c 1c c q 0c c 0m 01-m 0000r 12211≠=='=-≠+++++=---，，，阶导数的根，即：直到必是重根，则的是特征多项式设的特征多项式为：首先，原递归关系对应 m x q m x c x c x c x c x x r r r r r()()()()()()()()()()()()()()()()00,1,,2,1i 0d d d ,,,2,1)1(d 0000m i 101111-1≠+=-==<'='==++-+=--q c q q d m q d x m i x m x m x c q x c x x d x d x x d m i x c x r c x r x m mm i i i k r i r i i 的根，即：的根但不是重根，故也是的重根，则它也是的是特征多项式若故数：根的情况，引入下列函为了研究特征多项式重）（Why?()()()()nm tt n n t n n n b n b b a m x c n n f aβββ+++=•=** 21重根时的是当令递归关系的特解为()()()()[]()()()()()()n f r n b n b b c n b n b b c n b n b b c n b n b b n b n b b u n f u c u c u c u n f u c u c u c u u n b n b b n n b n b b a n n f s s r s s s s s s s s n r n r n n n r n r n n n n s s n m t t n n t =⎥⎥⎦⎤⎢⎢⎣⎡+++++++++++++++++++==++++=++++∆++++++==------*）（）（）（）（）（）（代入上式得：将则将其代入递归关系得：似的形式有类则递归关系的特解应具证明：要使等式成立，则递归关系-r -2-2-1-1-,102-r 1021-r 101r 10r -n 102-r 121-r 11r r -n r -n 2-n 121-n 11n nn 1010 ββββββββββββββββ()()()()()[]()[]{}()[]()[]{}()(){}()()()[]()()()()()()⎪⎪⎪⎪⎭⎪⎪⎪⎪⎬⎫⎪⎪⎪⎪⎩⎪⎪⎪⎪⎨⎧⎥⎥⎦⎤⎢⎢⎣⎡++++-+-++++++⎥⎥⎦⎤⎢⎢⎣⎡-++-+--+-+-+-++-+-=⎪⎪⎭⎪⎪⎬⎫⎪⎪⎩⎪⎪⎨⎧++-+-++++-+-+-+-++++-++-=⎥⎥⎦⎤⎢⎢⎣⎡++++++++++++++++------------------------001111111101111111111111111r 11r -n 01101-s 111011r -n 102-r 1021-r 101r 10r -n ])1()1([)1()1()1(-r -2-2-1-1-b c b c r b c r b c b r b r b r n b c r n b c r n r C b c r n b r n r C b r n b c r n b c r n b b r n b r n b c b r r n b r r n b c b r r n b r r n b r n b n b b c n b n b b c n b n b b c n b n b b r r s s r s s r r s s r s s r s s r s s r s s s r s s r s s s r s s s s r s s r s s s s r s s s r s s s s r s s r s s s s s s ββββββββββββββββββββ）（）（）（）（）（）（()()()()[]()()()[]()()()[]()()()()()次多项式。

第三章递推关系1.在平面上画n条无限直线,每对直线都在不同的点相交,它们构成的无限区域数记为f(n),求f(n)满足的递推关系.解： f(n)=f(n-1)+2f(1)=2,f(2)=4解得f(n)=2n.2.n位三进制数中,没有1出现在任何2的右边的序列的数目记为f(n),求f(n)满足的递推关系.解：设a n-1a n-2…a1是满足条件的n-1位三进制数序列，则它的个数可以用f(n-1)表示。

a n可以有两种情况：1）不管上述序列中是否有2，因为a n的位置在最左边，因此0和1均可选；2）当上述序列中没有1时，2可选；故满足条件的序列数为f(n)=2f(n-1)+2n-1 n 1,f(1)=3解得f(n)=2n-1(2+n).3.n位四进制数中,2和3出现偶数次的序列的数目记为f(n),求f(n)满足的递推关系.解：设h(n)表示2出现偶数次的序列的数目，g(n)表示有偶数个2奇数个3的序列的数目，由对称性它同时还可以表示奇数个2偶数个3的序列的数目。

则有h(n)=3h(n-1)+4n-1-h(n-1),h(1)=3 （1）f(n)=h(n)-g(n),f(n)=2f(n-1)+2g(n-1) （2）将（1）得到的h(n)=(2n+4n)/2代入（2），可得f(n+1)= (2n+4n)/2-2f(n),f(1)=2.4.求满足相邻位不同为0的n位二进制序列中0的个数f(n).解：这种序列有两种情况：1)最后一位为0，这种情况有f(n-3)个；2)最后一位为1，这种情况有2f(n-2)个；所以f(n)=f(n-3)+2f(n-2)f(1)=2,f(2)=3,f(3)=5.5.求n位0,1序列中“00”只在最后两位才出现的序列数f(n).解：最后两位是“00”的序列共有2n-2个。

f(n)包含了在最后两位第一次出现“00”的序列数，同时排除了在n-1位第一次出现“00”的可能；f(n-1)表示在第n-1位第一次出现“00”的序列数，同时同时排除了在n-2位第一次出现“00”的可能；依此类推，有f(n)+f(n-1)+f(n-2)+…+f(2)=2n-2f(2)=1,f(3)=1,f(4)=2.6.求n 位0,1序列中“010”只出现一次且在第n 位出现的序列数f(n).解：最后三位是“010”的序列共有2n-3个。

作业习题答案习题二证明：在一个至少有2人的小组中，总存在两个人，他们在组内所认识的人数相同。

证明：假设没有人谁都不认识：那么每个人认识的人数都为[1,n-1]，由鸽巢原理知，n个人认识的人数有n-1种，那么至少有2个人认识的人数相同。

假设有1人谁都不认识：那么其他n-1人认识的人数都为[1,n-2]，由鸽巢原理知，n-1个人认识的人数有n-2种，那么至少有2个人认识的人数相同。

证明：平面上任取5个坐标为整数的点，则其中至少有两个点，由它们所连线段的中点的坐标也是整数。

证明：方法一：有5个坐标，每个坐标只有4种可能的情况：（奇数，偶数）；（奇数，奇数）；（偶数，偶数）；（偶数，奇数）。

由鸽巢原理知，至少有2个坐标的情况相同。

又要想使中点的坐标也是整数，则其两点连线的坐标之和为偶数。

因为奇数+奇数 = 偶数；偶数+偶数=偶数。

因此只需找以上2个情况相同的点。

而已证明：存在至少2个坐标的情况相同。

证明成立。

方法二：对于平面上的任意整数坐标的点而言，其坐标值对2取模后的可能取值只有4种情况，即：(0,0) ,(0,1) ,(1,0), (1,1)，根据鸽巢原理5个点中必有2个点的坐标对2取模后是相同类型的，那么这两点的连线中点也必为整数。

一次选秀活动，每个人表演后可能得到的结果分别为“通过”、“淘汰”和“待定”，至少有多少人参加才能保证必有100个人得到相同的结果证明：根据推论，若将3*（100-1）+1=298个人得到3种结果，必有100人得到相同结果。

将一个矩形分成(m +1)行112m m +⎛⎫+⎪⎝⎭列的网格每个格子涂1种颜色，有m 种颜色可以选择，证明：无论怎么涂色，其中必有一个由格子构成的矩形的4个角上的格子被涂上同一种颜色。

证明：（1）对每一列而言，有（m+1）行，m 种颜色，有鸽巢原理，则必有两个单元格颜色相同。

（2）每列中两个单元格的不同位置组合有12m +⎛⎫⎪⎝⎭种，这样一列中两个同色单元格的位置组合共有 12m m +⎛⎫⎪⎝⎭种情况（3）现在有112m m +⎛⎫+⎪⎝⎭列，根据鸽巢原理，必有两列相同。

递推关系递归公式是用它自身来定义的一个公式，我们习惯称之为递推关系或递推式。

如正奇数序列可以用递推式描述为：f(n)=f(n-1)+2, n>1 且f(1)=1当n为很大的值时，直接用递推来计算f(n)会很麻烦，所以希望能够用一种封闭的式子来描述这个序列，从它入手可以直接计算f(n)。

如果找到这样一种封闭的式子，则称递推式已经解出。

下面的内容给出了求解基本的递推式的一些方法。

递推关系如果具有如下这种形式，则称为常系数线性齐次递推式：f(n)=a1f(n-1)+a2f(n-2)+…+a k f(n-k)这里f(n)称为k次的。

当一个附加项包括常数或者n的函数出现在递推中，那么它就称为非齐次的。

一、线性齐次递推式的求解令f(n)=a1f(n-1)+a2f(n-2)+…+a k f(n-k)的一般解含有f(n)=x n形式的特解的和。

用x n来代替上式中的f(n)，得到：x n =a1x n-1+a2 x n-2 +…+a k x n-k两边同时除以x n-k得到：x k =a1x k-1+a2 x k-2 +…+a k或者写成x k -a1x k-1-a2 x k-2 -…-a k =0以上两等式都称为原递推关系的特征方程。

下面我们只限于一阶和二阶的线性递推关系。

一阶齐次递推方程的解可以直接得到，令f(n)=af(n-1)，假定递推序列从f(0)开始，由于f(n)=af(n-1)=a2f(n-2)=…=a n f(0)所以f(n)=a n f(0)是递推的解。

如果递推的次数是2，那么特征方程变为x2-a1x-a2=0,令这个二次方程的根是r1和r2，递推的解是：f(n)=c1r1n+c2r2n(r1≠r2)f(n)=c1r n+c2nr n(r1=r2)代入序列初始的值f(n0)和f(n0+1)解方程得到c1和c2的值。

例1序列1,4,64,256,…可以用递推关系表示为f(n)=3f(n-1)+4f(n-2)，且f(0)=1,f(1)=4，求此递推式的解。