shttp://vcampus.fudan.edu.cn 用户名为学号,登录密码为本学期 〓选课密码。注意:选课密码要大写!
• http://vcampus.fudan.edu.cn • 用户名为学号，登录密码为本学期 选课密码。注意：选课密码要大写!
123递推关系 递推关系是离散变量之间变化规律中常 见的一种方式,与生成函数一样是解决 计数问题的有力工具。 数列u}如从某项后,u前项可推出un 的普遍规律,就称为递推关系。 g利用递推关系和初值在某些情况下可以 二求出序列的通项表达式un,称为该递推 关系的解。 不是所有的递推关系都可求出其解,只 是某些特殊类型有成熟解法
12.3 递推关系 • 递推关系是离散变量之间变化规律中常 见的一种方式，与生成函数一样是解决 计数问题的有力工具。 • 数列{un },如从某项后，un前k项可推出un 的普遍规律，就称为递推关系。 • 利用递推关系和初值在某些情况下可以 求出序列的通项表达式un，称为该递推 关系的解。 • 不是所有的递推关系都可求出其解，只 是某些特殊类型有成熟解法
-126:13世纪初意大利数学家 fibonacci研究过著名 的兔子繁殖数目问题设一对一雌一雄小兔刚满2个月 时,便可繁殖出一雌一雄一对小兔。以后每隔1个月生 对一雌一雄小兔。由一对刚出生的小兔开始饲养到 第n个月,有多少对兔子? 解:设第n个月有F对兔子,它由两部分组成 1)新生出的小兔,其数目等于能生小兔的大兔对数目 小兔满两个月才繁殖,数目为第(n2个月时的兔对数 目,即为Fn20 32原有小兔,其数目等于上月即第n-1个月)的兔对数 咱,即为Fn10 建立如下递推关系: n=Fn2+Fn1,并有初始条件:F=F2=1 这是一个带有初值的递推关系。 满足这种递推关系的数列称为 Fibonac数列
• 例12.6：13 世纪初意大利数学家 Fibonacci 研究过著名 的兔子繁殖数目问题:设一对一雌一雄小兔刚满2个月 时，便可繁殖出一雌一雄一对小兔。以后每隔1个月生 一对一雌一雄小兔。由一对刚出生的小兔开始饲养到 第n个月，有多少对兔子? • 解：设第n个月有Fn对兔子，它由两部分组成: • (1)新生出的小兔，其数目等于能生小兔的大兔对数目 • 小兔满两个月才繁殖，数目为第(n-2)个月时的兔对数 目，即为Fn-2。 • (2)原有小兔，其数目等于上月(即第 n-1个月)的兔对数 目，即为Fn-1。 • 建立如下递推关系: • Fn=Fn-2+Fn-1，并有初始条件：F1=F2 =1。 • 这是一个带有初值的递推关系。 • 满足这种递推关系的数列称为Fibonacci数列
例:设多重集S=(o·a,b,∞c},求a不相邻的m排 列数 解设不相邻的n排列数为an,则a1=3,a2=32-1=8 (减1是为了减去a这种情况), 当n3时 ,a不相 邻的所有n排列可分为互不相容 彐的两类: 1)第一个位置排b或c,剩下的n-个位置a不相邻, =(2)第一个位置排a,则第二个位置只能排b或c,而 剩下的n2个位置a不相邻, °·由加法原则,a不相邻的n排列数为: an=2an1+2an2,并有初始条件a1=3,a2=8, 这是一个带有初值的递推关系
• 例：设多重集S={·a,·b,·c}，求a不相邻的n-排 列数 • 解:设a不相邻的n-排列数为an，则a1=3, a2=3 2 -1=8 • (减1是为了减去aa这种情况)， • 当n≥3时，a 不相邻的所有n-排列可分为互不相容 的两类: • (1)第一个位置排b或c，剩下的n-1个位置a不相邻， • (2)第一个位置排a，则第二个位置只能排b或c，而 剩下的n-2 个位置a不相邻， • 由加法原则，a 不相邻的n-排列数为: • an =2an-1+2an-2，并有初始条件:a1=3,a2=8, • 这是一个带有初值的递推关系
·n个圆盘按半径大小依次套在圆柱A上现 另有圆柱B和C现要将圆盘全部移到柱子 B上,要求每次只能移动一个圆盘到另 个柱子上,且不允许大圆盘套在小圆盘之 上,求所需移动次数
• n个圆盘按半径大小依次套在圆柱A上,现 另有圆柱B和C.现要将圆盘全部移到柱子 B上,要求每次只能移动一个圆盘到另一 个柱子上,且不允许大圆盘套在小圆盘之 上,求所需移动次数
求解常系数线性递推关系的特征根 方法 定义123:数列an}满足递推关系 a=ha.tha+th.a h 为常 数=1,2,k,n≥k,h1≠0,称该递推关系为 a的k阶常系数线性齐次递推关系 形如 an=h1an1+h2an2+…,+hkan+f(m,h1为常 数=1,2,k,n≥k,h1=(0,称该递推关系为 n的k阶常系数线性非齐次递推关系
• 一、求解常系数线性递推关系的特征根 方法 • 定义12.3：数列{an }满足递推关系 • an=h1an-1+h2an-2+…+hkan-k , hi 为 常 数,i=1,2,…,k,n≥k, hk≠0，称该递推关系为 an的k阶常系数线性齐次递推关系。 • 形如 • an=h1an-1+h2an-2+…+hkan-k+f(n),hi 为 常 数,i=1,2,…,k,n≥k, hk≠0，称该递推关系为 an的k阶常系数线性非齐次递推关系
·k阶常系数线性齐次递推关系与微分方程 y()=h,y(k-l)+h2y(k-2)+.+hky h为常数,=1,2,,在结构上类似,而k 阶常系数线性非齐次递推关系与微分方 程 y()=h,y(k-1)+ h2 y(k-2)+. thky+f(n) h;为常数,=1,2,…,k,在结构上也类似,事 实上求解方法也与相应的微分方程类似
• k阶常系数线性齐次递推关系与微分方程 • y (k)=h1y (k-1)+ h2y (k-2)+…+hky • hi为常数,i=1,2,…,k,在结构上类似，而k 阶常系数线性非齐次递推关系与微分方 程 • y (k)=h1y (k-1)+ h2y (k-2)+…+hky+f(n) • hi为常数,i=1,2,…,k,在结构上也类似，事 实上求解方法也与相应的微分方程类似
·定义124:方程xh1x1h2xk2-h=0称 为k阶常系数线性齐次递推关系的特征方 程,它的k个根q1,q2,,q称为该递推关系 的特征根。其中q;(i=1,2,,k)是复数 定理124:qq≠0)是常系数线性齐次递推 关系的解的充要条件是:q是该递推关系 的特征根。 定理125:若k阶常系数线性齐次递推关系 的特征方程有k个互异的特征根 q1q2,,n,则该递推关系的通解为 an=c;q1"+c2q2+…+c(q1,其中c1c2…,c1为 任意常数
• 定义12.4:方程x k -h1x k-1 -h2x k-2 -…-hk =0称 为k阶常系数线性齐次递推关系的特征方 程,它的k个根 q1 ,q2 ,…,qk称为该递推关系 的特征根。其中qi (i=1,2,…,k)是复数。 • 定理12.4:q n (q≠0)是常系数线性齐次递推 关系的解的充要条件是: q是该递推关系 的特征根。 • 定理12.5:若k阶常系数线性齐次递推关系 的特征方程有 k 个互异的特征根 : q1 ,q2 ,…,qk， 则 该 递 推关 系 的通 解为 : an=c1q1 n+c2q2 n+…+ckqk n ,其中c1 ,c2 ,…ck为 任意常数
例:求an=2an1+2an2,并有初始条 件:a1=3,a2=8,递推关系的解。 解递推关系的特征方程为: x2-2x-2=0, 其根是:q1=1+31,q2=1-312。 由定理125知,递推关系的通解为: an=c1(1+312)叶e2(1-31)", 要满足初值条件,故有: c1(1+31)+e2(1-312)=3, C1(1+32)2+c2(1-312)2=8
• 例 : 求 an =2an-1+2an-2， 并有初始条 件:a1 =3,a2 =8,递推关系的解。 • 解:递推关系的特征方程为： • x 2 -2x-2=0, • 其根是：q1 =1+3 1/2 ，q2 =1-3 1/2 。 • 由定理12.5知，递推关系的通解为： • an=c1 (1+3 1/2 ) n+c2 (1-3 1/2 ) n , • 要满足初值条件，故有： • c1 (1+3 1/2 )+c2 (1-3 1/2 )=3, • c1 (1+3 1/2 ) 2+c2 (1-3 1/2 ) 2=8
定理126:若k阶常系数线性齐次递推关系 的特征方程有t个互异的特征根: m 192···t1m191m2 2,···9 m1为相应根的重数, 且m1+m2+m=k,则该递推关系的通解 为 ln=2∑cn/ i=1i=1 其中cn为任意常数≤m,1≤为任意常 数
• 定理12.6:若k阶常系数线性齐次递推关系 的 特 征 方 程 有 t 个 互 异 的 特 征 根 : q1 ,q2 ,…,qt，m1 ,m2 ,…,mt为相应根的重数， 且m1+m2+…+mt=k, 则该递推关系的通解 为: 其中cij为任意常数(1≤j≤mi ,1≤i≤t)为任意常 数。 = = − = t i m j n i j n ij i u c n q 1 1 1