当前位置：文档之家 › 组合数学 3.3常系数线性非齐次递推关系

组合数学 3.3常系数线性非齐次递推关系

  • 格式：ppt
  • 大小：69.50 KB
  • 文档页数：18

下载文档原格式

  / 18

合集下载

线性常系数递推关系

线性常系数递推关系


A B(n 1) r n xn , n0
C Dn r n xn, n0
因此通项表达式为： an C Dn r n ,
其中常数C, D可以利用初始条件来确定。
例如，若已知a0, a1，则 a0 C, a1 (C D)r D a1 r a0.
例1 求解递推关系：
an an-1 12an-2 0, a0 3, a1 26.
类似的，令母函数为G(x)=a0+a1x+a2x2+…，则
xk (ak C1ak1 C2ak2 L Cka0 ) 0 xk1 (ak1 C1ak C2ak1 L Cka1 ) 0
LL
__________ __________ ________ xn(an C1an1 C2an2 L Ckank) 0
L (an ban-1 can-2) xn ...
a0 (a1 ba0)x.
因此有
G(x)
a0 (a1 1 bx
ba0 ) cx 2
x
.
与分母相对应的方程 x2+bx+c=0 称为特征方程，它
的根
b b2 4c
r 1,2
2
称为特征根。
这样G(x)可以表示为：
G(x)
a0 (a1
1 1x 1 2x
1 k x
A1 (1 x)n A2 (2 x)n L Ak (k x)n
n0
n0
n0
( A11n
A2
n 2
L
Ak
n k
)
x
n
,
n0
因此通项表达式为：
an
A11n
A2
n 2
L
Ak
n k
组合数学(第二版)递推关系

组合数学(第二版)递推关系


递推关系
其次,证明an 是通解.若给定一组初始条件
可以仿照齐次方程通解的证明方法,证得相应于条件式 (3.2.11)的解一定可以表示为式 (3.2.10)的形式.
关于 的求法已经解决,这里的主要问题是求式(3.2.2) 的特解an * .遗憾的是寻求特 解还没有一般通用的方法.然而, 当非齐次线性递推关系的自由项f(n)比较简单时,采用 下面的 待定系数法比较方便.
递推关系 【例 3.4.2】 棋盘染色问题:给一个具有1行n 列的1×n
棋盘(见图3.4.1)的每一个 方块涂以红、蓝二色之一,要求相 邻的两块不能都染成红色,设不同的染法共有an 种,试 求an.
图 3.4.1 1×n 棋盘
递推关系
递推关系
【例3.4.3】 交替子集问题:有限整数集合Sn={1,2,…,n} 的一个子集称为交替的, 如果按上升次序列出其元素时,排列 方式为奇、偶、奇、偶、…….例如{1,4,7,8}和 {3,4,11}都是, 而{2,3,4,5}则不是.令gn表示交替子集的数目(其中包括空集), 证明
且有gn=Fn+2.
递推关系
证 显然,g1=2,对应S1 的交替子集为⌀和{1}.g2=3,对应S2 的交替子集为⌀、 {1}、{1,2}.
将Sn 的所有子集分为两部分: (1)Sn-1={1,2,…,n-1}的所有子集; (2)Sn-1的每一个子集加入元素n 后所得子集. 例如,n=4,S4={1,2,3,4}的所有子集划分为两类,即 (1)⌀、{1}、{2}、{3}、{1,2}、{1,3}、{2,3}、{1,2,3}; (2){4}、{1,4}、{2,4}、{3,4}、{1,2,4}、{1,3,4}、 {2,3,4}、{1,2,3,4}.
用升阶法求常系数非齐次线性递推关系的特解

用升阶法求常系数非齐次线性递推关系的特解

用升阶法求常系数非齐次线性递推关系的特解黄纯洁【摘要】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)。

组合数学递推关系

组合数学递推关系


(6.2.4)
如果方程组（6.2.4）有唯一解b'1 , b'2 ,, b'k ，这说明可以找到 这k个常数，使得
解. 考察方程组（6.2.4），它的系数行列式为这是著名的 Vandermonde行列式.因为 q1 , q2 ,, qk 互不相等，所以该行 列式不等于零，这也就是说方程组（6.2.4）有唯一解.
求解递推关系的常用方法 （1）迭代归纳法； （2）特征根法； （3）生成函数法；
例6.1.1（爬楼梯问题）一个小孩要爬上n阶 楼梯，每次可上一阶或两阶，问上n阶有多 少种上法？ 解：
显然登上1阶台阶有1种方法，登上2台阶有2种方法， f(1）=1，f(2)=2 ,称为递推关系的初始条件。 设有f(n) 种方法，要登上这n阶台阶，最后迈上一个台 阶或两个台阶完成. （1）若最后是迈上一个台阶完成的，则前面登上了n1阶台阶，有f(n-1) 种方法； （2）若最后是迈上两个台阶完成的，则前面登上了n2阶台阶，有f(n-2) 种方法，根据加法原理有递推关系： f(n)=f(n-1)+f(n-2) .
n n 1 n 1 n
例6.2.2
f (n) 2 f (n 1) 3 f (n 2) f (0) 1, f (1) 1 先求通解，特征方程是： x 2x 3 0
•
关于微分方程求解的已知结论:
1. 对于4次以及4次以下的方程,目前已有代数解法.(在复数 域内求解) 2. 阿贝尔定理: 5次以及更高次的代数方程没有一般的代数解法.
例6.2.1 求Fibonacci数的递推关系
n2 f (n) f (n 1) f (n 2) f (0) 1, f (1) 1 解：特征方程为x 2 x 1 0, 1 5 1 5 两个特征根分别是：x1 , x2 , 2 2 1 5 n 1 5 n 因此通解f (n) c1 ( ) c2 ( ) 2 2
线性常系数非齐次递推关系共54页文档

线性常系数非齐次递推关系共54页文档

—马克思 24、意志命运往往背道而驰，决心到最后会全部推倒。——莎士比亚
25、学习是劳动，是充满思想的劳动。——乌申斯基
谢谢！
线性常系数非齐次递推关系
56、死去何所道，托体同山阿。 57、春秋多佳日，登高赋新诗。 58、种豆南山下，草盛豆苗稀。晨兴 理荒秽 ，带月 荷锄归 。道狭 草木长 ，夕露 沾我衣 。衣沾 不足惜 ，但使 愿无违 。 59、相见无杂言，但道桑麻长。 60、迢迢新秋夕，亭亭月将圆。
21、要知道对好事的称颂过于夸大，也会招来人们的反感轻蔑和嫉妒。——培根 22、业精于勤，荒于嬉；行成于思，毁于随。——韩愈
3.3常系数线性非齐次递推关系

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


an＝c1an-1＋c2an-2＋…＋ckan-k＋F1(n)＋F2(n)
3.3.2 举例

a n 3a n 1 3 2 n 4n 例3.3.3 解递归 a 1 1
()

解(1)相伴齐次递推关系an＝3an-1 (☆)
(☆)的特征方程x－3＝0 (☆)的特征根 x＝3
根，所以得(＊)的一个特解形如
an＝n1(p1n＋p0)1n(p1,p0为待定系数) 代入a1＝1，a2＝3得
p1 p 0 1 2(2 p1 p 0) 3
1 p0 2 p 1 1 2
3.3.2 举例
故得(＊)的一个特解
1( 1 an＝n 2
3.3.2 举例

例3.3.1 解递归 a n a n 1 n
a 1 1
()

解(1)相伴齐次递推关系an＝an-1 (☆) (☆)的特征方程x－1＝0 (☆)的特征根 x＝1
(☆)的通解an＝a×1n＝a(a为任意常数)
3.3.2 举例

(2)由于F(n)＝n＝n×1n且s＝1是(☆)的1重
3.3.2 举例
(3) (＊)的通解
an＝a×3n－6×2n＋2n＋3(a为任意常数) (4)代入a1＝8得a＝5。故求得递归的解 an＝5×3n－6×2n＋2n＋3
作 业



1)1条直线将平面划分为2个部分，2条直线将 平面最多划分为4个部分， …，则n条直线 将平面最多划分为几个部分? 2)小兔子慧慧有12棵萝卜，它每天至少要吃1 棵，则当萝卜吃完之后，不同的吃萝卜的 情形有多少种？ 3)有两个同心圆，大圆周上有4个不同的点， 小圆周上有2个不同的点，则这6个点可确 定的不同直线最少有多少条？
常系数非齐次线性方程

常系数非齐次线性方程


05
常系数非齐次线性方程的数值解法的
应用实例
物理问题模拟
热传导方程
常系数非齐次线性方程可以用于描述一维热 传导过程，通过数值解法可以模拟温度随时 间变化的规律，预测物体在给定初始条件和 边界条件下的温度分布。
波动方程
在物理学中，波动方程也是一类常系数非齐 次线性方程，数值解法可以用于模拟波的传 播、反射、干涉等现象，如声波、电磁波等。
稳定性
当方程的解在时间趋于无穷大时，解的振幅趋于零，即解是 稳定的。
不稳定性
当方程的解在时间趋于无穷大时，解的振幅不趋于零，即解 是不稳定的。
解的振动性与非振动性
振动性
解在时间变化过程中呈现周期性变化 ，即解是振动的。
非振动性
解在时间变化过程中不呈现周期性变 化，即解是非振动的。
解的收敛性与发散性
步长与精度控制
总结词
在数值求解常系数非齐次线性方程时， 步长和精度是两个重要的控制参数，它 们直接影响到求解的精度和稳定性。
VS
详细描述
步长是每一步迭代的长度，过大的步长可 能导致求解不稳定或误差累积，过小的步 长则可能导致计算量过大。精度控制则是 设定求解的误差范围，以确定迭代何时停 止。在选择步长和精度时，需要根据具体 问题进行分析和试验，以找到合适的参数 设置。
收敛性
当时间趋于某一特定值时，解的振幅趋于零，即解是收敛的。
发散性
当时间趋于某一特定值时，解的振幅不趋于零，即解是发散的。
04
常系数非齐次线性方程的数值解法
欧拉方法
总结词
欧拉方法是数值求解常系数非齐次线性方程的经典方法之一，其基本思想是通过迭代逼近方程的解。
详细描述
欧拉方法是一种简单的数值求解常微分方程的方法，其基本思想是利用已知的初值来逐步逼近方程的解。在每一 步迭代中，根据前一步的解和方程的导数来计算下一步的解。欧拉方法简单易懂，但精度较低，迭代收敛速度较 慢。
组合数学(哈工大 第五章)

组合数学(哈工大 第五章)


. ..
. ..
. ..
. ..
.
任世军 (哈尔滨工业大学)
组合数学 递推关系
December 22, 2014
2 / 46
递推关系
. Definition . 设{an } 为一序列， 把该序列中an 和它前面几个ai (0 ≤ i ≤ n) 关联起来的 方程称做一个递推关系（递归关系）。 .
..
Example
..
. ..
. ..
.
. . . . . . . . . . . . .. .. .. .. .. .. .. .. .. .. .. .. ..
. ..
. ..
. ..
. ..
.
任世军 (哈尔滨ember 22, 2014
4 / 46
递推关系
. . 在一个平面上有一个圆和n 条直线， 这些直线中的每一条在圆内都同其他 的直线相交。如果没有多于三条的直线相交于一点， 试问这些直线将圆分 成多少个不同区域？ . 解: 设这n 条直线将圆分成的区域数为an ， 如果有n − 1 条直线将圆分 成an−1 个区域， 那么再加入第n 条直线与在圆内的其他n − 1 条直线相 交。显然， 这条直线在圆内被分成n 条线段， 而每条线段又将第n 条直线 在圆内经过的区域分成两个区域。这样， 加入第n 条直线后， 圆内就增加 了n 个区域。 而对于n = 0， 显然有a0 = 1， 于是对于每个整数 n， 可以建立 如下带初值的递推关系 a0 = 1, a1 = 2, an = an−1 + n
. ..
. ..
.
. . . . . . . . . . . . .. .. .. .. .. .. .. .. .. .. .. .. ..
关于常系数非齐次线性递推关系特解的注记

关于常系数非齐次线性递推关系特解的注记

关于常系数非齐次线性递推关系特解的注记唐善刚【摘要】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］得到的常系数线性齐次及非齐次递推关系的显式解是一个多重求和公式，由于该多重求和公式中的求和变量依赖于某个线性不定方程的所有非负整数解，进而导致显式解的多重求和公式在应用中的诸多不便。

【免费下载】李凡长版 组合数学课后习题答案 习题3

【免费下载】李凡长版 组合数学课后习题答案 习题3

第三章递推关系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个。

组合数学 第四章4常系数线性非齐次递推关系

组合数学 第四章4常系数线性非齐次递推关系

故该n递 推4, 关S系4 的4c解1 为6c2 4c3 c4 100 c4 6
Sn
n 1
7
n 2
12
n 3
6
n 4
1 n2 (n 1)2 4
思考
求an 4an1 2 • 5n 3 • 4n的通解
• P115， 27 • P117， 66
作业
an
A
A 2A
1
0
an* c 2n A 1
故 an 1，由定理5.6知上述递推关系式的通解为
an an an* 1 c 2n
又由初值条件a1 1得 1 c 21 1 c 1
故有
an 2n 1
§4.5§常5.3系常数系线数性线非性非齐齐次次递例推3 关系
例2、求递归关系
1i jt
即cij(i=1,2,…,t; j=1,2,…,mi)是由初值惟一确定，定理得证。
§4.3
常系数线性非齐次定义
§4.5常系数线性非齐次递推关系
定义 4.4
若{an}中相邻k+1项满足an+c1an-1+c2an-2+…+ ckan-k=f(n)，(n≥k)称之为{an}的k阶常系数线性 非齐次递推关系。其中ci(i=1,2,…,k)是常数， 且ck≠0，f(n)≠0 。
❖ 注：定理4.6指出，若要求一个常系数线性非齐次递推 关系式的通解，必须先求出这个递推关系所导出的常系数 线性齐次递推关系的通解，然后再求这个递推关系式的一 个特解，将其相加即可。 ❖ 然而，求一个非齐次线性递推关系的特解，通常没有系 统的方法，但当函数f(n)是某些特殊形式时，才有一些规 范的求法。
§4.5§常4系.3 数常系线数性Biblioteka 非性齐非次齐递次例推8关系例题

组合数学第六章递推关系


（1）等差数列（算术数列） ）等差数列（算术数列） h0, h0+q, h0+2q, …, h0+nq,… 递推关系： 递推关系：hn= hn-1+q 一般项： 一般项： hn= h0+nq 项和： 前n+1项和：sn= (n+1)h0+q(n)(n+1)/2 项和 （2）等比数列（几何数列） ）等比数列（几何数列） h0, qh0, q2h0, …, qnh0,… 递推关系： 递推关系：hn= qhn-1 一般项： 一般项： hn= qnh0 项和： 前n+1项和：sn= h0(1-qn+1)/(1-q) 项和
qn = c1qn−1 + c2qn−2 +L+ ck qn−k (n ≥ k)
因为 q ≠ 0 ，所以
qk = c1qk −1 + c2qk −2 +L+ ck ,
即是递推关系的特征根，反之亦然. • 如果 n是常系数线性齐次递推关系的解，还有吗？ 如果q 是常系数线性齐次递推关系的解，还有吗？ • 如果有，那么是否可以特征根构造递推关系的所 如果有， 有解？即从特解如何构造通解？ 有解？即从特解如何构造通解？
如果规定f(0)=1,则上式变成： f(n)=f(n-1)+f(n-2) (n≥2, n为整数) f(0)=1,f(1)=1 称满足这个式子的数列就成为Fibonacci数列， 数列中的项叫做Fibonacci数.
例6.1.3 （Hanoi塔问题）现有A，B，C三根立柱以及
n个大小不等的中空圆盘，这些圆盘自小到大套在A 柱上形成塔形，如图6.1.1所示，要把n个圆盘从A柱 上搬到C柱上，并保持原来的顺序不变，要求每次 只能从一根立柱上拿下一个圆盘放在另一根立柱上， 且不允许大盘压在小盘上，问至少要搬多少次 ？

递推关系

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

如正奇数序列可以用递推式描述为：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，求此递推式的解。

组合数学第二章5线性常系数非齐

p为待定系数，代入原递推关系得 p 4n 5 p 4n-1 6 p 4n-2 42 4n 化简得 42 p 42 16 p 16 故所求特解为 a *n 16 4n 4n 2
n
2.8 线性常系数非齐次递推关系
例4 求解递推关系 an - 5an-1 6an-2 2n 的特解
例 2， 求解递推关系 an an1 7n 的特解
解：如果我们设a *n p1n p2 代入原递推关系得 ( p1n p2 ) -[ p1 ( n -1) p2 ] 7n
于是 p1 =7n
2.8 线性常系数非齐次递推关系
我们很直观的看出上式解不出p1 和 p2.这是 因为当原递推关系的特征根是1时.如果所设的特 解中n的最高次幂的次数与f(n)的次数一样时,代入 原递推关系后,等式左边的n的最高次幂就会消去. 因此等式左边的多项式比右边的多项式的次数低. 为此 在设特解时要将n的最高次幂提高,并且可以不 设常数项
n
2.9
Stirling数
推广: n个有区别的球放到m个有区别的盒子 里，要求m个盒子放的球数分别是
n1 , n2 ,, nm (n n1 n2 nm )
其不同方案数用下式表示：
n n1n 2 n m
(9.1)
2.9
Stirling数
计算如下
从n个有区别的球中取出n1个放到第1个盒子里 去，其选取方案数为C(n,n1)；当第1个盒子的n1 个球选定后,第2个盒子里的n2个球则是从n- n1个 中选取的，其方案数应为 C(n-n1,n2),第3个盒子 的n3个球则是从余下的n-n1– n2个球中选取，其 方案数C(n- n1-n2, n3)…..

组合数学32常系数线性齐次递推关系


3.2.4 递推(3.2.1)特征根互不同 例 解递归 解 递推推关系an＝an-1－an-2 (＊) (＊)的特征方程为x2－x＋1＝0 (＊)的特征根x1 , x2 (＊)的通解
3.2.4 递推(3.2.1)特征根互不同
STEP 01
STEP 02
把a1＝1, a2＝0代入通解得
单击此处添加大标题内容
单击此处添加正文，文字是您思想的提炼，为了演示发布的良好效果，请言简意赅地阐述您的观点。您的内容已经简明扼要，字字珠玑，但信息却千丝万缕、错综复杂，需要用更多的文字来表述；但请您尽可能提炼思想的精髓，否则容易造成观者的阅读压力，适得其反。正如我们都希望改变世界，希望给别人带去光明，但更多时候我们只需要播下一颗种子，自然有微风吹拂，雨露滋养。恰如其分地表达观点，往往事半功倍。当您的内容到达这个限度时，或许已经不纯粹作用于演示，极大可能运用于阅读领域；无论是传播观点、知识分享还是汇报工作，内容的详尽固然重要，但请一定注意信息框架的清晰，这样才能使内容层次分明，页面简洁易读。如果您的内容确实非常重要又难以精简，也请使用分段处理，对内容进行简单的梳理和提炼，这样会使逻辑框架相对清晰。为了能让您有更直观的字数感受，并进一步方便使用，我们设置了文本的最大限度，当您输入的文字到这里时，已濒临页面容纳内容的上限，若还有更多内容，请酌情缩小字号，但我们不建议您的文本字号小于14磅，请您务必注意。单击此处添加正文，文字是您思想的提炼，为了演示发布的良好效果，请言简意赅地阐述您的观点。您的内容已经简明扼要，字字珠玑，但信息却千丝万缕、错综复杂，需要用更多的文字来表述；但请您尽可能提炼思想的精髓，否则容易造成观者的阅读压力，适得其反。正如我们都希望改变世界，希望给别人带去光明，但更多时候我们只需要播下一颗种子，自然有微风吹拂，雨露滋养。恰如其分地表达观点，往往事半功倍。当您的内容到达这个限度时，或许已经不纯粹作用于演示，极大可能运用于阅读领域；无论是传播观点、知识分享还是汇报工作，内容的详尽固然重要，但请一定注意信息框架的清晰，这样才能使内容层次分明，页面简洁易读。如果您的内容确实非常重要又难以精简，也请使用分段处理，对内容进行简单的梳理和提炼，这样会使逻辑框架相对清晰。

常系数非齐线性递推式的一种图解法

常系数非齐线性递推式的一种图解法
薛访存;田长生
【期刊名称】《广东技术师范学院学报(社会科学版)》
【年(卷),期】1990(000)004
【摘要】无
【总页数】3页(P19-21)
【作者】薛访存;田长生
【作者单位】无
【正文语种】中文
【相关文献】
1.关于常系数线性递推式解的注记 [J], 杜学诚
2.常系数齐线性递推式的另一解法 [J], 薛访存;廖学儒;田长生
3.关于一类非常系数线性递推式的解的显式表示 [J], 余长安
4.常系数非刘次线性递推式的显式解 [J], 刘治国
5.线性常系数递推关系的通项的一种表达式 [J], 邓波
因版权原因，仅展示原文概要，查看原文内容请购买。

  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

3.3.2 举例
(2)由于F(n)＝1＝1×1n且s＝1是(☆)的0重 根，所以得(＊)的一个特解形如 an＝n0×p×1n ＝p(p为待定系数) 代入(＊)得p＝－1 故得(＊)的一个特解an＝－1
3.3.2 举例
(3) (＊)的通解 an＝a×2n－1(a为任意常数)
代入a1＝1得a＝1 (4)求得递归的解an＝2n－1
an＝n1(p1n＋p0)1n(p1,p0为待定系数)
代入a1＝1，a2＝3得
p1 p0 1 2(2 p1 p0) 3
p0
1 2
p1
1 2
3.3.2 举例
故得(＊)的一个特解
an＝n1(
1 2
n＋
1 2
)1n ＝ 1
2
n2＋ 1
2
n
(3) (＊)的通解
an＝a＋
1 2
n2＋
1 2
n
3.3.2 举例
定理3.3.3若an＝x(n)和an＝y(n)分别是递推关系 an＝c1an-1＋c2an-2＋…＋ckan-k＋F1(n) an＝c1an-1＋c2an-2＋…＋ckan-k＋F2(n) 的解，其中c1,c2,…,ck(ck≠0)是实数常数，F1(n)与 F1(n)是只依赖于n且不恒为0的函数， 则an＝x(n)＋y(n)为递推关系 an＝c1an-1＋c2an-2＋…＋ckan-k＋F1(n)＋F2(n) 的解
3.3.2 举例
例3.3.1 解递归 an an1 n ()
a1
1
解(1)相伴齐次递推关系an＝an-1 (☆) (☆)的特征方程x－1＝0
(☆)的特征根 x＝1
(☆)的通解an＝a×1n＝a(a为任意常数)
3.3.2 举例
(2)由于F(n)＝n＝n×1n且s＝1是(☆)的1重
根，所以得(＊)的一个特解形如
3.3.1 非其次递推关系
定理3.3.2 设常系数线性非齐次递推关 an＝c1an-1＋c2an-2＋…＋ckan-k ＋F(n)
其中c1,c2,…,ck是实数常数，ck≠0； 且F(n)＝(btnt＋bt-1nt-1＋…＋b1n ＋b0)Sn 其中b1,b2,…,bt和S是实数常数。 当S是相伴的线性齐次递推关系的特征方程的 m(m≥0)重根时，存在一个下述形式的特解： an＝nm(ptnt＋pt-1nt-1＋…＋p1n＋p0)Sn 其中p1,p2,…,pt为待定系数。
3.3.2 举例
例3.3.3 解递归 an 3an1 3 2n 4n ()
a1 1
解(1)相伴齐次递推关系an＝3an-1 (☆) (☆)的特征方程x－3＝0 (☆)的特征根 x＝3 (☆)的通解an＝a×3n(a为任意常数)
3.3.2 举例
(2)分别求an＝3an-1＋3×2n (◇) an＝3an-1－4n (△)的一个特解
(◇)的一个特解形如b×2n (b为常数) 将其代入(◇)得b＝－6 故求得(◇)的一个特解an＝－6×2n
类似求得(△)的一个特解an＝2n＋3 故求得(＊)的一个特解an ＝－6×2n＋(＊)的通解 an＝a×3n－6×2n＋2n＋3(a为任意常数)
(4)代入a1＝8得a＝5。故求得递归的解 an＝5×3n－6×2n＋2n＋3
(a为任意常数)
代入a1＝1得a＝0
(4)求得递归的解an＝
1 2
n2＋
1 2
n
3.3.2 举例
例3.3.2 解Hanoi问题的递归，即
an 2an1 1 ()
a1
1
解(1)相伴齐次递推关系an＝2an-1 (☆)
(☆)的特征方程x－2＝0
(☆)的特征根 x＝2
(☆)的通解an＝a×2n(a为任意常数)
相伴的齐次递推关系 an＝c1an-1＋c2an-2＋…＋ckan-k (3.3.2)
3.3.1 非其次递推关系
定理3.3.1
若an＝x(n)为递推关系
(3.3.1)相伴的齐次递推关系(3.3.2)的通
解， an＝y(n)为递推关系(3.3.1)的一个 特解，则an＝x(n) ＋y(n)为递推关系 (3.3.1)的通解。
3.3常系数线性非其次递推关系 3.3.1 非其次递推关系 3.3.2 举例
3.3.1 非其次递推关系
常系数线性非其次递推关系 an＝c1an-1＋c2an-2＋…＋ckan-k ＋F(n) (3.3.1) 其中c1,c2,…,ck是实数常数，ck≠0； F(n)是只依赖于n且不恒为0的函数。