组合数学 3.2常系数线性齐次递推关系
- 格式：ppt
- 大小：105.00 KB
- 文档页数：15
下载文档原格式
合集下载
线性常系数齐次递推
i
2 1 2
k 1
k 2
1 C x C x
其中
Ck x G x C j x
k j 0
k 1
k 1 j j i 0
a x
i
i
C0 1
2.7 线性常系数齐次递推关系
令
P x C j x
j 0
k 1
k 1 j j i 0
例4 an - 4an -1 4an -2 0, a0 1, a1 4.
解 : 特征方程：x 4 x 4 0 ( x 2)
2 2
特征根 r 2(2重根)
所以 an ( A B n)2n
再根据初始条件a0 A 1, a1 2( A B) 4 可解得A 1, B 1
K ( x) 0, 即 x 2 bx c 0 称为特征方程，
它的根为 r 1,2 称为特征根. b b 2 4ac 2
2.7 线性常系数齐次递推关系
于是 D( x) 1 bx cx (1- r1x)(1- r2 x)
2
下面就其根来进行讨论:
1) r1 r2的情形
根据定理可知，an c1 4n c2 (-3)n
再根据初始条件 c1 c2 a0 3 c1 5 c1 4 c2 (-3) a1 26 c2 2
2.7 线性常系数齐次递推关系
例2 an an 1 an 2 , a1 1, a2 0.
和 an ban -1 can -2 0 对应的分母1 bx cx 2在 求 an 的过程中扮演了十分重要的角色，用 D( x)表示，即D( x) 1 bx cx .
2 1 2
k 1
k 2
1 C x C x
其中
Ck x G x C j x
k j 0
k 1
k 1 j j i 0
a x
i
i
C0 1
2.7 线性常系数齐次递推关系
令
P x C j x
j 0
k 1
k 1 j j i 0
例4 an - 4an -1 4an -2 0, a0 1, a1 4.
解 : 特征方程：x 4 x 4 0 ( x 2)
2 2
特征根 r 2(2重根)
所以 an ( A B n)2n
再根据初始条件a0 A 1, a1 2( A B) 4 可解得A 1, B 1
K ( x) 0, 即 x 2 bx c 0 称为特征方程，
它的根为 r 1,2 称为特征根. b b 2 4ac 2
2.7 线性常系数齐次递推关系
于是 D( x) 1 bx cx (1- r1x)(1- r2 x)
2
下面就其根来进行讨论:
1) r1 r2的情形
根据定理可知，an c1 4n c2 (-3)n
再根据初始条件 c1 c2 a0 3 c1 5 c1 4 c2 (-3) a1 26 c2 2
2.7 线性常系数齐次递推关系
例2 an an 1 an 2 , a1 1, a2 0.
和 an ban -1 can -2 0 对应的分母1 bx cx 2在 求 an 的过程中扮演了十分重要的角色，用 D( x)表示，即D( x) 1 bx cx .
递推关系式
递推关系式一、引言递推关系式是数学中的一个重要概念，它描述了一个序列中后一项与前一项之间的关系。
通过递推关系式，我们可以根据已知的初始条件逐步计算出序列中的各个项，从而揭示数学规律和模式。
递推关系式在各个领域都有广泛应用，如数列、递归函数和动态规划等。
二、数列与递推关系式2.1 数列的定义数列是由一系列按照一定规律排列的数字组成的序列。
数列中的每个数字称为项，而数列中的规律称为数列的通项公式。
通过数列的通项公式，我们可以方便地计算数列中的任意项。
2.2 递推关系式的定义递推关系式是数列中后一项与前一项之间的关系式。
一般地，递推关系式可以表示为：a n+1=f(a n)，其中n为项的序号，a n表示第n项，f表示递推函数。
2.3 递推关系式的作用递推关系式可以帮助我们计算数列中的任意项，从而揭示数列中的规律和模式。
通过分析递推关系式，我们可以得到数列的闭式表达式，即直接根据项的序号计算出项的值的公式。
三、递推关系式的形式递推关系式可以具有多种不同的形式，根据具体情况选择适合的形式进行表示。
下面列举了几种常见的递推关系式形式。
3.1 线性递推关系式线性递推关系式是一种最简单的递推关系式形式，其通项公式可以表示为：a n+1=a n+c，其中c为常数。
线性递推关系式描述了数列中的每个项与前一项之间的恒定差值关系。
3.2 二次递推关系式二次递推关系式是一种形式更为复杂的递推关系式。
其通项公式可以表示为：a n+1=a n2+b，其中b为常数。
二次递推关系式描述了数列中的每个项与前一项的平方加上常数之间的关系。
3.3 递归函数递归函数是一种特殊的递推关系式形式，其通项公式可以表示为：a n=f(a n−1)。
递归函数通过直接调用自身来计算数列中的各个项。
四、递推关系式的应用4.1 数列的求和通过递推关系式，我们可以方便地求解数列的前n项和。
方法是先计算出数列的第n项，然后通过求和公式计算前n项和。
4.2 数列的性质分析递推关系式可以帮助我们深入地分析数列的性质。
组合数学递推关系
(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
第二节常系数线性齐次递推关系
23
23
例2
求解递推关系
f (n) (k f (2) k(k
2) f (n 1) (k 1) f (n 2) 1), f (3) k(k 1)(k 2).
(n
4)
解 递推关系的特征方程为：x2 (k 2)x (k 1) 0,
特征根为:
q1 k 1, q2 1,
所以递推关系的通解为
下面研究当特征根有重根时，递推关系的通解． 引理1. 若q为k阶常系数线性齐次递推关系(1)
的二重特征根，则 nqn为递推关系的解．
证明 令
P(x) xk C1xk1 C2 xk2 Ck1x Ck ,
Pn (x) xnk P(x) xn C1xn1 C2 xn2 Ck xnk , 因为q为P(x)的二重根，所以q也为Pn(x)的二重根， 从而q为 Pn '(x)的一重根，也为 xPn '(x)的一重根． 又由于
称{bn} 为满足初始条件的特解，显然满足初始条件的特 解是唯一的．
f (n) C1 f (n 1) C2 f (n 2) Ck f (n k) (n k) (1)
定义2 方程 xk C1xk1 C2xk2 Ck 0 称为递推关系(1)的 特征方程，它的根称为递推关系的特征根．
3.
它的特征方程为：x2 2x 3 0,
特征根为: x1 3, x2 1,
所以递推关系的通解为 g(t) C1(3)t C2 (1)t .
代人初值有
3CC11CC22
0, 3.
解方程组，得
C1
3 4
, C2
3 4
,
所以递推关系的解为 g(t) 3 3t 3 (1)t. 44
从而有
f (n) A(k 1)n B(1)n.
常系数线性齐次矩阵列及函数列递归关系的解法
证明 用 As ij 表示矩阵 As 的位于第 i 行第 j 列位
是递归关系 (3)的通解，其中 C1 , C 2 , , C k 为任意 s t 常 数矩阵。 证明 用 As ij 表示矩阵 As 的位于第 i 行第 j 列位
置的元素。由(3)，则有
置的元素。由(3)，则有
An ij
a1 An 1 ij a 2 An 2 ij a k An k ij ，
An ij
a1 An 1 ij a 2 An 2 ij a k An k ij ，
i 1,2, , s; j 1,2, , t
x k a1 x k 1 a2 x k 2 ak 1 x ak 0
，
共 有 t 个 不 同 的 根 q1 , q 2 , , qt ， 它 们 的 重 数 分 别 为
An ij C1 ij q1n C 2 ij q 2n C k ij q kn
由
它们的重数分别为
m1 , m2 , , mt ，
A0 C11 C 21 A1 C11 C12 C 21 2 2 A2 C11 2C12 C 21 2
则递归关系(4)的通解为：
f n (t ) F1 (n, t ) F2 (n, t ) Ft (n, t ) ，
n k
(3)
An C1 1n C2 2n 2 2n 3 2n 2 2 n 1 。 5 2 n 1 10 5 2 n 1 2 n 1 定理 2 若矩阵列递归关系(3)的特征方程(2)共有 t
个不同的根
定义 2
是递归关系 (3)的通解，其中 C1 , C 2 , , C k 为任意 s t 常 数矩阵。 证明 用 As ij 表示矩阵 As 的位于第 i 行第 j 列位
置的元素。由(3)，则有
置的元素。由(3)，则有
An ij
a1 An 1 ij a 2 An 2 ij a k An k ij ，
An ij
a1 An 1 ij a 2 An 2 ij a k An k ij ，
i 1,2, , s; j 1,2, , t
x k a1 x k 1 a2 x k 2 ak 1 x ak 0
，
共 有 t 个 不 同 的 根 q1 , q 2 , , qt ， 它 们 的 重 数 分 别 为
An ij C1 ij q1n C 2 ij q 2n C k ij q kn
由
它们的重数分别为
m1 , m2 , , mt ，
A0 C11 C 21 A1 C11 C12 C 21 2 2 A2 C11 2C12 C 21 2
则递归关系(4)的通解为：
f n (t ) F1 (n, t ) F2 (n, t ) Ft (n, t ) ，
n k
(3)
An C1 1n C2 2n 2 2n 3 2n 2 2 n 1 。 5 2 n 1 10 5 2 n 1 2 n 1 定理 2 若矩阵列递归关系(3)的特征方程(2)共有 t
个不同的根
定义 2
组合数学之常系数递归关系
7
(m,n)
Pk
P2 (0,1) (0,0) P1
(1,0)
图4.2
8
这样建立了从(1,0)点到 这样建立了从(1,0)点到(m,n)点的一条 点到( 路径与从(0,1)到 点且过y=x上点 路径与从(0,1)到(m,n)点且过y=x上点 的路径之间的一一对应关系. 的路径之间的一一对应关系. 利用以上结论, 利用以上结论, 可以用两种方式得到 题目中要求的路径数目N 题目中要求的路径数目N: (1) N=从(0,0)点到(m,n)点的总路径数 (0,0)点到 点到( - 2×从(1,0)点到(m,n)点的路径数 (1,0)点到 点到( N=C(m+n,m)-2C(m+n-1,m-1) =C(m+n, 2C(m+n-1,m =C(m+n=C(m+n-1, m)-C(m+n-1,m-1). C(m+n-1,m
19
对于(4.1)中的 阶齐次递归关系: 对于(4.1)中的r阶齐次递归关系: 中的r H n a1 H n1 a 2 H n 2 a r H n r = 0 我们定义如下的一元 r 次方程: 次方程:
10
例3 音乐会票价为50元一张, 排队买票的 音乐会票价为50元一张 元一张, 顾客中有m位持50元的钞票 位持100 元的钞票, 顾客中有m位持50元的钞票, n位持100 元的钞票. 售票处没有50元的零钱 元的零钱. 元的钞票. 售票处没有50元的零钱. 问 有多少种排队的办法使购票能顺利进 不出现找不出钱的状态, 行, 不出现找不出钱的状态, 假定每位 顾客只买一张票, 而且m 顾客只买一张票, 而且m≥n. 分析: 可以用m+n维 1向量来表示一种 分析: 可以用m+n维0, 1向量来表示一种 排队状态, 令该向量为: 排队状态, 令该向量为: (a1,a2,…, am+n), 其中a =1,2,… m+n. 其中ai=0 或1, i=1,2,…,m+n. ai=0表示第i个顾客持50元的票款; =0表示第 个顾客持50元的票款 表示第i 元的票款; ai=1表示第i个顾客持100元的票款. =1表示第 个顾客持100元的票款 表示第i 元的票款.
(m,n)
Pk
P2 (0,1) (0,0) P1
(1,0)
图4.2
8
这样建立了从(1,0)点到 这样建立了从(1,0)点到(m,n)点的一条 点到( 路径与从(0,1)到 点且过y=x上点 路径与从(0,1)到(m,n)点且过y=x上点 的路径之间的一一对应关系. 的路径之间的一一对应关系. 利用以上结论, 利用以上结论, 可以用两种方式得到 题目中要求的路径数目N 题目中要求的路径数目N: (1) N=从(0,0)点到(m,n)点的总路径数 (0,0)点到 点到( - 2×从(1,0)点到(m,n)点的路径数 (1,0)点到 点到( N=C(m+n,m)-2C(m+n-1,m-1) =C(m+n, 2C(m+n-1,m =C(m+n=C(m+n-1, m)-C(m+n-1,m-1). C(m+n-1,m
19
对于(4.1)中的 阶齐次递归关系: 对于(4.1)中的r阶齐次递归关系: 中的r H n a1 H n1 a 2 H n 2 a r H n r = 0 我们定义如下的一元 r 次方程: 次方程:
10
例3 音乐会票价为50元一张, 排队买票的 音乐会票价为50元一张 元一张, 顾客中有m位持50元的钞票 位持100 元的钞票, 顾客中有m位持50元的钞票, n位持100 元的钞票. 售票处没有50元的零钱 元的零钱. 元的钞票. 售票处没有50元的零钱. 问 有多少种排队的办法使购票能顺利进 不出现找不出钱的状态, 行, 不出现找不出钱的状态, 假定每位 顾客只买一张票, 而且m 顾客只买一张票, 而且m≥n. 分析: 可以用m+n维 1向量来表示一种 分析: 可以用m+n维0, 1向量来表示一种 排队状态, 令该向量为: 排队状态, 令该向量为: (a1,a2,…, am+n), 其中a =1,2,… m+n. 其中ai=0 或1, i=1,2,…,m+n. ai=0表示第i个顾客持50元的票款; =0表示第 个顾客持50元的票款 表示第i 元的票款; ai=1表示第i个顾客持100元的票款. =1表示第 个顾客持100元的票款 表示第i 元的票款.
组合数学(哈工大 第五章)
. ..
. ..
. ..
. ..
.
任世军 (哈尔滨工业大学)
组合数学 递推关系
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
. ..
. ..
.
. . . . . . . . . . . . .. .. .. .. .. .. .. .. .. .. .. .. ..
组合数学讲义及答案 3章 递推关系
后两项求和：
m 1 m 1 2m j 2 j r r r ＋ m 1 r j j 0
m2 m 1
＝r
2m 2 j j 0
j j r ＝ r
n 2 2
§3.2 常系数线性递推关系
常系数的线性递推关系：
a n c1 a n1 c 2 a n 2 c k a n k 0,
或
c k
0
(3.2.1)
an c1an 1 c2 an 2 ck an k f n ， （ ck 0 ）
(3.2.2) 分别称为 k 阶齐次递推关系和 k 阶非齐次递推关系。 其中 f(n) 称为自由项。 显 然 ， 式 （ 3.2.1 ） 至 少 有 一 个 平 凡 解 a n 0n 0,1,2, ，而人们更关心的是它的非零解。
n k k k r ，求{an}所满足的递推关 k 0
n n n n - 1 n - 2 2 r r ＋…＋ 2 r 2 n 为偶数： a n ＝ n 0 1 2 2
a n 2a n1 1 , a 1 1
3／75
(3.1.3)
《组合数学》
第三章 递推关系
求解
a n ＝ 2n 1
例3.1.2 （Lancaster 战斗方程）两军打仗，每支军队在每 天战斗结束时都清点人数，用 a0 和 b0 分别表示在战斗打响前 第一支和第二支军队的人数，用 an 和 bn 分别表示第一支和第 二支军队在第 n 天战斗结束时的人数，那么，an－1－an 就表示 第一支军队在第 n 天战斗中损失的人数，同样，bn－1－bn 表示 第二支军队在第 n 天战斗中损失的人数。 假设：一支军队所减少的人数与另一支军队在每天战斗开 始前的人数成比例，则
组合数学求解递推关系2
性质3
对线性齐次递推式：
hn a1hn1 a2 hn 2 ... ak hn k 0 (ak 0)
设 ak x k , 可以吗？
相应的特征方程为：
x k a1 x k 1 ... ak 1 x ak 0
若 q 是特征方程的解， 则 q n 是齐次递推式的解 .
性质4
对线性齐次递推式
hn a1hn1 a2 hn 2 ... ak hn k 0 (ak 0)
若 q1 , q2 , ... qk 是特征方程的 k个不同的
特征根，则 hn c1q1 c2 q2 ... ck qk
n n n
是齐次递推式的通解 .
对初始条件 h0 , h1 , ...， hk -1， 可以唯一确定 hn c1q1 c2 q2 ... ck qk
总结
对线性齐次递推式
hn a1hn1 a2 hn 2 ... ak hn k 0 (ak 0)
若 q1 , q2 , ... qt 是特征方程的全部互异 的特征根， qi 是si 重根（ i 1,2,..., t )，则 hn H n 其中 Hn
(i ) (1)
错位排列 :
Dn ( n 1)( Dn-1 Dn-1 )
二阶变系数线性齐次式。
Dn nDn-1 ( 1)n
一阶变系数线性非齐次式。 例2 Fibonacci数列 f n f n-1 f n- 2 , f 0 0, f1 1 二阶常系数线性齐次式。 例3 等比数列 hn qhn1 一阶常系数齐次 等差数列 hn hn1 d 一阶常系数非齐次 阶乘数列 hn n hn1 一阶变系数齐次
最新整理高三数学递推关系的求解.docx
最新整理高三数学递推关系的求解递推关系的求解一基本概念定义：确定的数列称为递推数列。
（为其的阶）二基本解法（1）（2）（3）常系数线性齐次递推关系将（2）称为（1）的特征方程若是（2）的重根，则（1）的个特解分别为个特解的线性组合就是（1）的通解。
设找到，使令可得 .从而为的根。
结论：，若有两个不动点，则，这里。
若只有一个不动点，则，这里三常用思想：1．不动点，特征根2．无理化有理（取对数，化新数列）3．多元化少元4．高次化低次5．高阶降低阶6．非线性化线性7．非齐次化齐次8．猜想试解P103 例6 在正项数列中，求通项公式。
解对两边取对数，得即这说明数列是首项为，公比为的等比数列，则有故P104例8 设数列满足且求证：是完全平方数。
证由式可得并代入式，得两式相减由方程，得那么通解为由 ,代入上式解出，得因为为正偶数，所以，是完全平方数.P106 例9 数列中， .解构建数列 .故化简得所以数列是以2为首项，1/2为公比的等比数列.所以P107 例10已知满足，且，求 .解: 是二阶线性非齐次递推数列，先设法将它转化为一阶递推关系，故条件变形为：可见是常数列，逐次递推得即P107 例11设满足，求 .解：，解方程 ,得于是由定理10得，则：由已知可得，解得P108 例12已知满足，，且，求 .解：，故两式相减得即则，根据特征方程求解.P108 例13设正数列满足 ,求 .解：把递推关系改写为①令，则①为②对②两边取对数，得③令，则③为利用不动点性质有即故其中，即是以为首项，为公比的等比数列，由等比数列的通项公式可知为常数数列，逆推上去，得，则，故是以为首项，为公比的等比数列，由等比数列的通项公式可知 .P109 例14数列定义为：，求证：对任意的自然数，，表示不超过的最大整数。
证明：递推关系较为复杂，结论又未给出的表达式，不妨通过归纳法探索的表达式：当时，，当时，，……………由此可以猜想： . ①问题转化为证明这一猜想，再证可被3整除。
组合数学课程简介
《组合数学》课程简介
“组合数学”课程是数学与应用数学专业必修的学科专业课课程。
它主要研究一组离散对象满足一定条件的安排的存在性，以及这种安排的构造、枚举个数及优化问题。
组合数学源远流长，它起源于古代的数学游戏和美学消遣，以无穷的魅力激发人们的聪明才智和数学兴趣。
随着计算机科学，数学通讯理论，规划论和实验设计等近代科学技术的发展，组合数学分析已成为很多前言学科的基础。
特备是计算机科学的飞速发展，给组合数学注入了新的生机和活力。
组合数学的离散性及算法与计算机的联姻在现代科学技术中正发挥着越来越大的作用，并且在计算机科学、管理科学、电子工程、数字通讯等诸多领域具有极为广泛的应用。
通过教学使学生掌握解决组合问题的思路和方法，培养“组合思维”、熟练“组合技巧”、提高解决较复杂组合问题的能力。
结合数学竞赛问题，阐述组合数学的基本思想、基本方法和常用技巧，推动中学数学竞赛的普及与发展。
组合数学课程主要内容包括：一、排列与组合，包括加法原理和乘法原理，排列与组合，二项式系数，有限集的子集类，分配；二、抽屉原理，包括抽屉原理的简单形式，抽屉原理的加强形式，抽屉原理的一般形式；三、容斥原理，包括容斥原理的简单形式，在数论中的应用，错位，容斥原理的一般形式；四、递推关系，包括Fibonacci数列，常系数线性齐次递推关系，迭代与递归，差分表；
五、生成函数，包括形式幂级数，生成函数，线性递推关系，一个几何学问题，可重组合与可重排列；六、幻方，包括幻方的概念与有关性质，奇阶幻方的构造方法，偶阶幻方的构造方法。
3.2常系数线性齐次递推关系
2
也都是递推关系(3.2.1)的解。
3.2.4 递推(3.2.1)特征根互不同
特征方程(3.2.2)有k个不同的根x1,x2,…,xk 递推关系(3.2.1)的通解 an＝A1x1n＋A2x2n＋…＋Akxkn 共轭复根x1＝peiө，x2＝pe-iө 递推关系(3.2.1)的通解an＝A1pncosnө ＋ A2pnsinnө ＋A3x3n ＋…＋Akxkn
定理3.2.3 如果特征方程(3.2.2)有k 个不同的根x1,x2,…,xk (可有共轭虚 x ( 根)，则 an＝A1x1n＋A2x2n＋…＋Akxkn 是递推关系(3.2.1)的通解，其中 A1,A2,…,Ak为任意的常数。
3.2.4 递推(3.2.1)特征根互不同
例3.2.1 解递归 f 0=0, 1=1 f
3.2.4 递推(3.2.1)特征根互不同
把f0＝0, f1＝1代入通解得
A1 + A 2 = 0 1 + 5 1− 5 A1 + 2 A 2 = 1 2
5 A1 = 5 =− 5 A2 5
因此所求递归的解为
5 1+ 5 5 1− 5 fn= − 5 5 2 2
定理3.2.5 设x1,x2,…xt-1,xt(t＜k)是特征方程 (3.2.2)的t个不同根，且xt为m(m＝k－t＋1) 重根，则 an＝A1x1n＋A2x2n＋…＋At-1xt-1n ＋n0Atxtn＋n1At+1xt+1n＋ …＋nm-1Akxkn 是递推关系(3.2.1)的通解，其中A1,A2,…,Ak 为任意的常数。
3.3.5 递推(3.2.1)特征根有重根
例3.2.3 解递归 a 0=0,a =1, 2=2, 3=3 a a
递推关系
递推关系递归公式是用它自身来定义的一个公式，我们习惯称之为递推关系或递推式。
如正奇数序列可以用递推式描述为：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，求此递推式的解。
线性常系数递推关系
n0
所以通项体现式为：an Ar1n Br2n ,
其中常数A, B能够利用待定系数法拟定，或者利用
初始条件(A+B=a0, Ar1+Br2=a1)来拟定。
(1)’ 假如r1≠r2，且是一对共轭复根，则能够假设
r1 ei , r2 e-i
这Байду номын сангаас就有：
an Ar1n Br2n A
e i
解得特征根为 r1 r2 2.
所以通项体现式能够设为：an ( A Bn) 2n.
代入初始条件有
a0 A 1,
A 1, B 1.
a1 2( A B) 4,
所以通项体现式为： an (1 n) 2n.
接下来讨论一般旳k阶线性常系数齐次递推关系：
an C1an1 C2an2 Ckank 0.
(2)
其中 C1,C2, ,Ck (Ck 0), d0,d1, ,dk 1 都是常数，
则(1)称为一种k阶线性常系数递推关系，
(2)称为初始条件。
假如b(n)=0，则称为齐次旳， 不然称为非齐次旳。
先考虑二阶线性常系数齐次递推关系，即
an b an1 c an2 0, c 0
令母函数为G(x)=a0+a1x+a2x2+…，则
1 r1x
ba0 ) x
1 r2 x
.
下面要根据特征根来进行分类讨论。
(1) 假如r1≠r2，则
G(x)
a0 (a1 ba0 ) x
1 r1x1 r2 x
A 1 r1 x
B 1 r2 x
A (r1 x)n B (r2 x)n
n0
n0
( Ar1n Br2n ) xn ,
组合数学-第十节：递推关系
而且这n个元素依上面列出的顺序所能作出的一切可能的积彼此不同，其个数记为 ，求 满足的递推关系。
解例如，对于 ，符合题意的积有2个：
所以 。
如果在 的某些字母间加上括号，但不改变字母间的相互位置关系，使得这n个字母间的乘法可以按所加括号指明的运算方式进行运算，那么 就是加括号的方法的个数。
最外层的两对括号形如
（4.3.2）
定理4.3.1 k阶常系数线性非齐次递推关系（4.3.1）的通解是递推关系（4.3.1）的特解加上其相应的齐次递推关系（4.3.2）的通解。
证明设 是递推关系（4.3.1）的特解， 是递推关系（4.3.2）的通解，则
所以， 是递推关系（4.3.1）的解。
反之，任给递推关系（4.3.1）的一个解 ，与上类似，可以证明 是递推关系（4.3.2）的解，从而 可以表示成 与递推关系（4.3.2）的解之和。
（4.4.1）
解由递推关系（4.4.1）可以得到
将上式乘以 后再与（4.4.1）式相加，得
（4.4.2）
如此我们得到了二阶齐次递推关系（4.4.2），它需要两个初值才能确定解。将 代入递推关系（4.4.1），得
所以有
它的特征方程为
解得两个特征根为
于是，通解为
由初值 ，求得 。故
（2）将变系数的一阶线性递推关系化为常系数线性递推关系。
例2在信道上传输由 三个字母组成的长为n的字符串，若字符串中有两个 连续出现，则信道就不能传输。令 表示信道可以传输的长为n的字符串的个数，求 满足的递推关系。
解信道上能够传输的长度为 的字符串可分成如下四类：
（1）最左字符为b；（2）最左字符为c；
（3）最左两个字符为ab；（4）最左两个字符为ac。
由此，我们得出 的前5项满足
解例如，对于 ，符合题意的积有2个：
所以 。
如果在 的某些字母间加上括号，但不改变字母间的相互位置关系，使得这n个字母间的乘法可以按所加括号指明的运算方式进行运算，那么 就是加括号的方法的个数。
最外层的两对括号形如
（4.3.2）
定理4.3.1 k阶常系数线性非齐次递推关系（4.3.1）的通解是递推关系（4.3.1）的特解加上其相应的齐次递推关系（4.3.2）的通解。
证明设 是递推关系（4.3.1）的特解， 是递推关系（4.3.2）的通解，则
所以， 是递推关系（4.3.1）的解。
反之，任给递推关系（4.3.1）的一个解 ，与上类似，可以证明 是递推关系（4.3.2）的解，从而 可以表示成 与递推关系（4.3.2）的解之和。
（4.4.1）
解由递推关系（4.4.1）可以得到
将上式乘以 后再与（4.4.1）式相加，得
（4.4.2）
如此我们得到了二阶齐次递推关系（4.4.2），它需要两个初值才能确定解。将 代入递推关系（4.4.1），得
所以有
它的特征方程为
解得两个特征根为
于是，通解为
由初值 ，求得 。故
（2）将变系数的一阶线性递推关系化为常系数线性递推关系。
例2在信道上传输由 三个字母组成的长为n的字符串，若字符串中有两个 连续出现，则信道就不能传输。令 表示信道可以传输的长为n的字符串的个数，求 满足的递推关系。
解信道上能够传输的长度为 的字符串可分成如下四类：
（1）最左字符为b；（2）最左字符为c；
（3）最左两个字符为ab；（4）最左两个字符为ac。
由此，我们得出 的前5项满足
- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
递推关系(3.2.1)的特征根
教学ppt
3
3.2.3 递推(3.2.1)的解
定理3.2.1 非零复数q是特征方程(3.2.2)的 根，当且仅当an＝qn是递推关系(3.2.1)的解
xk－c1xk-1－c2xk-2－…－ck-1x－ck＝0 (3.2.2) x＝q
an＝qn
an＝c1an-1＋c2an-2＋…＋ckan-k (3.2.1)
是递推关系(3.2.1)的通解，其中A1,A2,…,Ak
为任意的常数。
教学ppt
14
3.3.5 递推(3.2.1)特征根有重根
例3.2.3 解递归 aa0n==-02,aan1-=11,aa2n=-42,a3=3
解 递推推关系an＝－2an-1－an-4 (＊) (＊)的特征方程为x4＋2x2＋4＝0 (＊)的特征根x1＝x2＝i , x3＝x4＝－i
把f0＝0, f1＝1代入通解得
A1 A2 0
1 2
5
A1
1 2
5
A2
1
A 1
5 5
A
2
5 5
因此所求递归的解为
n
n
f
n
51 5
5
2
4 递推(3.2.1)特征根互不同
定理3.2.3中，若特征方程(3.2.2)有共
轭复根x1＝peiө，x2＝pe-iө
例3.2.1 解递归 f0=0,f1=1 fn=f f n-1+ n-2
解 递推推关系fn＝fn-1＋fn-2 (＊)
(＊)的特征方程为x2－x－1＝0
(＊)的特征根x1＝1 + 2 5 , x2＝1 - 2 5
(＊)的通解
n
n
f n=A1125教学pp+t A2125
7
3.2.4 递推(3.2.1)特征根互不同
递推关系(3.2.1)的通解
an＝A1x1n＋A2x2n＋…＋Akxkn
共轭复根x1＝peiө，x2＝pe-iө
递推关系(3.2.1)的通解an＝A1pncosnө ＋
A2pnsinnө ＋A3x3n ＋…教＋学ppAt kxkn
10
3.2.4 递推(3.2.1)特征根互不同
例3.2.2 解递归a1=1,a2=0 an=an-1 an-2
其中c1,c2,…,ck是实数教常学p数pt ， ck≠0
4
3.2.3 递推(3.2.1)的解
定理3.2.2 若h1(n),h2(n),…,hk(n)是递 推关系(3.2.1)的解，则它们的线性组合
A1h1(n)＋A2h2(n)＋…＋Akhk(n)也是递 推关系(3.2.1)的解，其中A1, A2,…, Ak为 常数。
此时x1n＝pneinө，x2n＝pne-inө都是递推 关系(3.2.1)的解。再由定理3.2.2知：
1 2
x1n＋
1 2
x2n＝pncosnө,
1 2
x1n－12
x2n＝pnsinnө
也都是递推关系(3.2.1)的解。
教学ppt
9
3.2.4 递推(3.2.1)特征根互不同
特征方程(3.2.2)有k个不同的根x1,x2,…,xk
(＊a )的n = 通A 1 c 解o s n 2 + n A 2 c o s 教n 学2 ppt A 3 s in n 2 + n A 4 s in n 2 15
3.3.5 递推(3.2.1)特征根有重根
把a1＝0, a2＝1,a3＝2, a4＝3代入通解得
A1 0
A
3
A
1
A
2
4
3.2常系数线性齐次递推关系
3.2.1 递推关系(3.2.1)
3.2.2 递推(3.2.1)的特征方程
3.2.3 递推(3.2.1)的解
3.2.4 递推(3.2.1)特征根互不同
3.3.5 递推(3.2.1)特征根有重根
教学ppt
1
3.2.1 递推关系(3.2.1)
常系数k阶线性齐次递推关系 an＝c1an-1＋c2an-2＋…＋ckan-k (3.2.1) 其中c1,c2,…,ck是实数常数， ck≠0
教学ppt
5
3.2.4 递推(3.2.1)特征根互不同
定理3.2.3 如果特征方程(3.2.2)有k
个不同的根x1,x2,…,xk (可有共轭虚 根)，则
an＝A1x1n＋A2x2n＋…＋Akxkn
是递推关系(3.2.1)的通解，其中
A1,A2,…,Ak为任意教的学pp常t 数。
6
3.2.4 递推(3.2.1)特征根互不同
系(3.2.1)的解。
教学ppt
13
3.3.5 递推(3.2.1)特征根有重根
定理3.2.5 设x1,x2,…xt-1,xt(t＜k)是特征方程 (3.2.2)的t个不同根，且xt为m(m＝k－t＋1) 重根，则
an＝A1x1n＋A2x2n＋…＋At-1xt-1n
＋n0Atxtn＋n1At+1xt+1n＋ …＋nm-1Akxkn
3
A2 sin 3
1
A1
cos
2
3
2
A2 sin 3
0
A
1
1
A 2
3 3
因此所求递归的解为
an
cosn
3
3sinn
33
教学ppt
12
3.3.5 递推(3.2.1)特征根有重根
定理3.2.4 设q(q≠0)是递推关系(3.2.1)
的特征方程(3.2.2)的m(m≥2)重根，则
an＝ntqn(t＝0,1,2,…,m－1)都是递推关
A
2
1
2
A 3 3 A 4 3
因此所求递归的解为
A1 0
A A
2 3
1 3
A 4 2
a n nco sn 2 3 sinn 2 2 nsinn 2
教学ppt
16
教学ppt
17
教学ppt
18
教学ppt
19
教学ppt
20
教学ppt
2
3.2.2 递推(3.2.1)的特征方程
把an＝xn (x≠0)代入递推关系(3.2.1)得 xn＝c1xn-1＋c2xn-2＋…＋ckxn-k 用xn-k除上式两边得
xk＝c1xk-1＋c2xk-2＋…＋ck-1x＋ck xk－c1xk-1－c2xk-2－…－ck-1x－ck＝0 (3.2.2) (3.2.2)即为递推关系(3.2.1)的特征方程
解 递推推关系an＝an-1－an-2 (＊) (＊)的特征方程为x2－x＋1＝0
(＊)的特征根x1
1+ 3i 2
ei 3
,
x2
12
3i
e
i 3
(＊)的通解 an=A1cosn3+A2sinn3
教学ppt
11
3.2.4 递推(3.2.1)特征根互不同
把a1＝1, a2＝0代入通解得
A1
cos