http://vcampus.fudan.edu.cn 用户名为学号，登录密码为本学期选课密码。注意：选课密码要大写!

12.3 递推关系 递推关系是离散变量之间变化规律中常见的一种方式，与生成函数一样是解决计数问题的有力工具。 数列{un},如从某项后，un前k项可推出un的普遍规律，就称为递推关系。 利用递推关系和初值在某些情况下可以求出序列的通项表达式un，称为该递推关系的解。 不是所有的递推关系都可求出其解，只是某些特殊类型有成熟解法。

例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={·a,·b,·c}，求a不相邻的n-排列数 解:设a不相邻的n-排列数为an，则a1=3, a2=32-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 n个圆盘按半径大小依次套在圆柱A上,现另有圆柱B和C.现要将圆盘全部移到柱子B上,要求每次只能移动一个圆盘到另一个柱子上,且不允许大圆盘套在小圆盘之上,求所需移动次数.

一、求解常系数线性递推关系的特征根方法 定义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(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,在结构上也类似，事实上求解方法也与相应的微分方程类似。

定义12.4:方程xk-h1xk-1-h2xk-2-…-hk=0称为k阶常系数线性齐次递推关系的特征方程,它的k个根 q1,q2,…,qk称为该递推关系的特征根。其中qi(i=1,2,…,k)是复数。 定理12.4:qn(q≠0)是常系数线性齐次递推关系的解的充要条件是: q是该递推关系的特征根。 定理12.5:若k阶常系数线性齐次递推关系的特征方程有 k 个互异的特征根: q1,q2,…,qk，则该递推关系的通解为: an=c1q1n+c2q2n+…+ckqkn,其中c1,c2,…ck为任意常数。

例:求an=2an-1+2an-2，并有初始条件:a1=3,a2=8,递推关系的解。 解:递推关系的特征方程为： x2-2x-2=0, 其根是：q1=1+31/2，q2=1-31/2。 由定理12.5知，递推关系的通解为： an=c1(1+31/2)n+c2(1-31/2)n, 要满足初值条件，故有： c1(1+31/2)+c2(1-31/2)=3, c1(1+31/2)2+c2(1-31/2)2=8

定理12.6:若k阶常系数线性齐次递推关系的特征方程有 t 个互异的特征根: q1,q2,…,qt，m1,m2,…,mt为相应根的重数，且m1+m2+…+mt=k, 则该递推关系的通解为: 其中cij为任意常数(1≤j≤mi,1≤i≤t)为任意常数。

例:求解递推关系 an+an-1-3an-2-5an-3-2an-4=0,n≥4 a0=1,a1=a2=0,a3=2 解:该递推关系的特征方程是 x4+x3-3x2-5x-2=0, 其特征根是-1,-1,-1,2。

k阶常系数线性非齐次递推关系的通解与k阶常系数线性非齐次微分方程的通解类似, 也是齐次通解与特解之和，即： an=a'n+a n* 其中a'n是k阶常系数线性非齐次递推关系所对应的k阶常系数线性齐次递推关系 an=h1an-1+h2an-2+…+hkan-k=0的通解， a n*是k阶常系数线性非齐次递推关系的特解。

(1)当f(n)是n的t次多项式时，对应的特解形式为： a n*=P1nt+P2nt-1+…+Ptn+Pt+1 其中P1,P2,…,Pt,Pt+1为待定系数。 (2)当f(n)是n的形式时，若不是对应的齐次递推关系的特征根，则对应的特解是Pn，其中P为待定系数; 若是对应的齐次递推关系的m重特征根，则对应的特解是 Pnmn，其中P为待定系数。

例12.10:求解递推关系 an+2an-1=n+1,n1, a0=2 解:该递推关系导出的齐次线性递推关系 an+2an-1=0的特征方程是： x+2=0 其特征根是-2。 通解为a'n=c(-2)n 又因f(n)=n+1，特解具有形式 a n*=P1n+P2

例: 求h(n)=2h(n-1)+1, 并有初始条件:h(1)=1的递推关系解。 例:求解递推关系 an=an-1+7n,n2, a1=2

二、生成函数方法求解递推关系 在求解递推关系时，生成函数法也是一个有力的工具。用生成函数法求解递推关系的关键是用f(x)表示an的生成函数，即： 然后将{an}的递推关系代入右边，便得到一个关于f(x)的方程， 解此方程，并将所得的解展开成幂级数，就可得到 an 的表达式。

f(x)=a0+a1x+a2x2+…+anxn+… 则： -xf(x) =-a0x-a1x2-a2x3…-anxn+1-… 例:用生成函数法求解递推关系: an=an-1+9an-2-9an-3,n≥3 a0=0, a1=1, a2=2 解:设{an}的生成函数为： f(x)=a0+a1x+a2x2+…+anxn+… 则： -xf(x) =-a0x-a1x2-a2x3…-anxn+1-… -9x2f(x) =-9a0x2-9a1x3-9a2x4-…-9an-2xn-… 9x3f(x) =9a0x3+9a1x4+…+9an-3xn+… 以上四式相加得： (1-x-9x2+9x3)f(x)=a0+(a1-a0)x+(a2-a1-9a0)x2+(a3-a2-9a1+9a0)x3+…+(an-an-1-9an-2+9an-3)xn+… 因为a0=0,a1=1, a2=2，且当n≥3时,an-an-1-9an-2+9an-3=0， (an=an-1+9an-2-9an-3) 所以有： (1-x-9x2+9x3)f(x)=x+x2 即：f(x)=(x+x2)/(1-x-9x2+9x3) =(x+x2)/((1-x)(1+3x)(1-3x)) 而1/(1-x)=1+x+x2+…+xn+…； 1/(1+3x)=1-3x+32x2-…+(-1)n3nxn+… 1/(1-3x)=1+3x+32x2+…+3nxn+…； 因此有：

即Fn-10.618Fn。 黄金分割。 例:用生成函数法求12.6的递推关系解： Fn=Fn-2+Fn-1， F1=F2=1。 f(x)=F0+F1x+F2x2+…+Fnxn+…则： -xf(x) =-F0x-F1x2-F2x3…-Fnxn+1-… -x2f(x) =-F0x2-F1x3-F2x4-…-Fn-2xn-… 以上三式相加得： (1-x-x2)f(x)=F1x+(F2-F1)x2+(F3-F2-F1)x3+(F4-F3-F2)x4+…+(Fn-Fn-1-Fn-2)xn+… 因为F1=1, F2=1，且当n≥3时,Fn-Fn-1-Fn-2=0， (Fn=Fn-1+Fn-2) 所以有： (1-x-x2)f(x)=x 即：f(x)=x/(1-x-x2) 即Fn-10.618Fn。 黄金分割。

作业: P253:10,14(1)(3),15 测验： 1.设f是集合A到集合A的内射，但不是满射，求A的最小基数,说明理由。 2.一个人步行了11小时，共走了45公里，已知他第一小时走6公里，而最后一小时只走了3公里，用鸽笼原理证明：一定存在连续3个小时，使得在这3个小时内至少走了12公里.