《组合数学》 第三章 递推关系
第三章 递推关系
1. 递推关系及其分类 2. 建立应用问题的递推关系的方法 3. 求解线性常系数递推关系的特征根方法 4. 求解递推关系的其它方法 5. 三个典型数列及其应用 §3.1 基本概念
（一） 递推关系
一个关系到an和某些个ai?i?n?的方程式，称为递推关系，
记作
【定义3.1.1】（隐式）对数列?aii?0?和任意自然数n，
F?a0,a1,?,an??0
22222例 an?an?1?an?2???a0?n?0
an?3an?1?2an?2???2a1?1?0
【定义3.1. 1?】（显式） 对数列?aii?0?，把an与其之前若干项联系起来的等式对所有n≥k均成立（k为某个给定的自然数），称该等式为?ai?的递推关系，记为
＇ an?F?an?1,an?2,?,an?k? （3.1.1）
例 an?3an?1?2an?2???2a1?1
1／72
《组合数学》 第三章 递推关系
（二） 分类
（1） 按常量部分：
① 齐次递推关系：指常量＝0，如
Fn?Fn?1?Fn?2；
② 非齐次递推关系，即常量≠0，如hn?2hn?1?1。 （2） 按ai的运算关系：
① 线性关系，F是关于ai的线性函数，如（1）中的Fn与hn均是如此；
② 非线性关系，F是ai的非线性函数，如hn?h1hn?1?h2hn?2???hn?1h1。 （3） 按ai的系数：
① 常系数递推关系，如（1）中的Fn与hn；
② 变系数递推关系，如pn?npn?1，pn?1之前的系数是随着n而变的。 （4） 按数列的多少：
① 一元递推关系，其中的方程只涉及一个数列，如（3.1.1）和（3.1.1）＇均为一元的；
② 多元递推关系，方程中涉及多个数列，如
?an?7an?1?bn?1 ??bn?7bn?1?an?1（5）显式与隐式：
yn?1?xn?1? ?yn?h?yn?1?2?yn?1??2／72
《组合数学》 第三章 递推关系
（三） 定解问题
【定义3.1.2】（定解问题）称含有初始条件的递推关系为定解问题，其一般形式为
?F?a0,a1,?,an??0, （3.1.2） ??a0?d0,a1?d1,?,ak?1?dk?1解递推关系，指根据式（3.1.1）或（3.1.2）求an的与a0、a1、?、an－1无关的解析表达式或数列{an}的母函数。 （四） 例
【例3.1.1】（Hanoi塔问题）n个圆盘按从小到大的顺序一次套在柱A上。规定每次只能从一根柱子上搬动一个圆盘到另一根柱子上，且要求在搬动过程中不允许大盘放在小盘上，而且只有A、B、C三根柱子可供使用。用an表示将n个盘从柱A移到柱C上所需搬动圆盘的最少次数，试建立数列{an}的递推关系。
A B C
（解）特例：a1＝1，a2＝3，对于任何n≥3。 一般情形：：
第一步，将套在柱A的上部的n－1个盘按要求移到柱B上，共搬动了an?1次；
3／72
《组合数学》 第三章 递推关系
第二步，将柱A上的最大一个盘移到柱C上，只要搬动一次；
第三步，再从柱B将n－1个盘按要求移到柱C上，也要用an?1次。
?an?2an?1?1,由加法法则： ? （3.1.3）
?a1?1求解 an＝2n?1
【例3.1.2】（Lancaster战斗方程）两军打仗，每支军队在每天战斗结束时都清点人数，用a0和b0分别表示在战斗打响前第一支和第二支军队的人数，用an和bn分别表示第一支和第二支军队在第n天战斗结束时的人数，那么，an－1－an就表示第一支军队在第n天战斗中损失的人数，同样，bn－1－bn表示第二支军队在第n天战斗中损失的人数。
假设：一支军队所减少的人数与另一支军队在每天战斗开始前的人数成比例，则
?an?1?an?Abn?1 ??bn?1?bn?Ban?1常量A、B——度量每支军队的武器系数
?an?an?1?Abn?1 （3.1.4） ??bn?bn?1?Ban?1——含有两个未知量的一阶线性递归关系组。
?n?k?k【例3.1.3】设an????k??r，求{an}所满足的递推关
?k?0?系。
4／72
?n??2???《组合数学》 第三章 递推关系
（解）?x?——下整数函数。即不大于x的最大整数。
?n?n???n??n-1??n-2?22?r2 ???????r?rn为偶数：an＝?＋?＋?0??1??2?n???????????2??n?1?n-1???n??n-1??n-2?222an＝?n为奇数：?0?????1??r???2??r＋?＋?n-1?r
???????????2?分两种情况：当n为偶数时，令n＝2m，则
?n?1??n?2?＝?＝m－1 ????2??2?m?2m?k?kan＝???k??r
?k?0??2m?m?1?2m?k?k?m?m＝??0??＋???k??r＋??m??r ??k?1?????2m?m?1?2m?k?1?k?r ＝??0??＋????k??k?1??m?1?2m?k?1?k?m?m＋???k?1??r＋??m??r
???k?1?前两项求和：
?2m?m?1?2m?k?1?km?1?2m?k?1?k???r???r ＝?0?????????kk??k?1???k?0??n?1???2???k?0?n?1?k?k??r?an?1 ??k??后两项求和：
5／72