3、递推方程递推关系的建立例1有一个小孩要爬上有n个台阶的楼梯，他一步可以爬一个台阶或者两个台阶。这个小孩爬上这n个台阶楼梯的不同方法的数目记作an，求an的递推关系。解：例2设平面上有n条直线，其中每对直线都相交，但任意三条直线都不交于一点。这样的n条直线把平面分成的区域个数记作an，求an的递推关系。解：递推关系的建立例3在信道上传输由a,b,c三个字母组成的长为n的字符串，若字符串中有两个a连续出现，则信道就不能传输。令an表示信道可以传输的长为n的字符串的个数，求an满足的递推关系。解：递推关系的建立例4把n个相同的球放入k个不同盒子中，每个盒子
4、中的球不少于2个又不多于4个。其不同的放法的数目记作an,k，求an,k的递推关系，如果这n个球取自3种颜色的球如何？解：递推关系的建立例5用an表示包含偶数个0和偶数个1的n位三进制序列的个数，用bn表示包含偶数个0和奇数个1的n位三进制序列的个数，用cn表示包含奇数个0和偶数个1的n位三进制序列的个数。求关于an,bn,cn(n=1,2...)的递推关系。解：递推关系的建立例6平面上有一点P，它是n个区域D1,D2,...Dn的共同交界点，现取k种颜色对n个区域着色，要求相邻区域着不同的颜色，试求着色方案。解：递推关系的建立r阶递推关系的一般形式
5、若e(n)=0，称其为齐次递推关系式若e(n)≠0，称其为非齐次递推关系式当ci(n)=ci时（i=1,2,…,r）称为常系数递推关系第6-7讲递推关系递推关系的定义递推关系的建立递推关系的求解常系数线性齐次递推关系求解非齐次递推关系的求解非线性递推关系的求解母函数解递推方程递推关系的求解经典解法母函数解法迭代法置换法归纳法相加削去法常系数齐次线性递推关系一般形式：特征方程：（式1）引理1设m是非零实数或复数，则mn是递推关系式的解的充要条件是：m是上述递推关系式1的特征方程的特征根。引理2如果an[1],an[2]都是递推关系式的解，B1,B2是常
6、数，则B1an[1]+B2an[2]也是上述递推关系式1的解。定理若m1,m2,…,mr是特征方程的特征根，B1,B2,…,Br是常数，则也是上述递推关系式1的解。定义如果递推关系式1的每个解an[s]都可以选择一组常数B1’,B2’,…,Br’使得成立，则称是递推关系式1的通解，其中：B1’,B2’,…,Br’是任意常数。无重特征根定理：设m1,…,mr是递推关系式1的r个互不相等的特征根，则：是递推关系式1的通解。有重特征根定理：设m1,m2,…,mi是递推关系式1的全部互不相等的特征根，其重数分别为e1,e2,…,ei(e1+e2+…+ei=r
7、)则递推关系式对应mi部分的通解是：而递推关系式1的通解为：递推关系求解过程列出特征方程对特征方程进行求解根据特征根写出通解根据初始条件确定待定系数常系数齐次线性递推关系的求解例7an-3an-1+3an-2-an-3=0,且a0=0,a1=1,a2=3,求an=?解：例810个数字(0~9)和4个运算符(+,-,,)组成14个元素，求由其中的n个元素构成的排列组成的算术表达式的个数（含除数为0的情况）解：例9n阶行列式常系数齐次线性递推关系的求解定理r阶线性常系数非齐次递推关系的通解an是该非齐次递推关系的一个特解an[p]，加上其相应的齐次递
8、推关系的通解an[c]即多项式型非齐次递推关系一般形式定理：当l是相应的齐次递推关系的k重特征根时（若l不是该齐次递推关系的根时，k=0）是该非齐次递推关系的一个特解。求解过程求齐次递推关系的通解求非齐次递推关系的特解列出非齐次递推关系的通解形式根据初始条件确定待定系数多项式型非齐次递推关系例10an=2an-1+1,a1=1解：例11an=an-1+2(n-1),a0=2,求an=?解：多项式型非齐次递推关系指数型非齐次递推关系一般形式定理：当b是对应的齐次递推关系的k重特征根时（若b不是特征根，则k=0）该非齐次递推关系的一个特解的形式为例12a
9、n-2an-1=2n-1,a1=3解：例13求n位十进制正整数中出现偶数个5的个数解：指数型非齐次递推关系求
