3章递推关系VIP专享VIP免费

第三章递推关系§3.1基本概念（一）递推关系定义3.1.1（隐式）对数列0iai和任意自然数n，一个关系到na和某些个niai的方程式，称为递推关系，记作010naaaF,,,(3.1.1)例022022212naaaannn01223121aaaannn定义3.1.1＇（显式）对数列0iai，把na与其之前若干项联系起来的等式对所有n≥k均成立（k为某个给定的自然数），称该等式为ia的递推关系，记为knnnnaaaFa,,,21(3.1.1)＇例1223121aaaannn（二）分类（1）按常量部分：①齐次递推关系：指常量＝0，如21nnnFFF；②非齐次递推关系，即常量≠0，如121nnhh。（2）按ia的运算关系：①线性关系，F是关于ia的线性函数，如（1）中的nF与nh均是如此；②非线性关系，F是ia的非线性函数，如112211hhhhhhhnnnn。（3）按ia的系数：①常系数递推关系，如（1）中的nF与nh；②变系数递推关系，如1nnnpp，1np之前的系数是随着n而变的。（4）按数列的多少①一元递推关系，其中的方程只涉及一个数列，如(3.1.1)和(3.1.1)＇均为一元的；②多元递推关系，方程中涉及多个数列，如111177nnnnnnabbbaa（5）显式与隐式以上所给出的例子都是显式的或者可以化为显式关系（如（1）中的hn）。而在求微分方程的数值解时，还会碰到如下的隐式递推关系：11112nnnnnyxyhyy（三）定解问题定义3.1.2（定解问题）称含有初始条件的递推关系为定解问题，其一般形式为111100100kkndadadaaaaF,,,,,,,(3.1.2)所谓解递推关系，就是指根据式(3.1.1)或(3.1.2)求an的与a0、a1、⋯、an－1无关的解析表达式或数列{an}的母函数。（四）例例3.1.1（Hanoi塔问题）这是组合学中著名的问题。N个圆盘按从小到大的顺序一次套在柱A上，如图3.1.1所示。规定每次只能从一根柱子上搬动一个圆盘到另一根柱子上，且要求在搬动过程中不允许大盘放在小盘上，而且只有A、B、C三根柱子可供使用。用an表示将n个盘从柱A移到柱C上所需搬动圆盘的最少次数，试建立数列{na}的递推关系。ABC图3.1.1Hanoi塔问题（解）易知，a1＝1，a2＝3，对于任何n≥3，现设计搬动圆盘的算法如下：第一步，将套在柱A的上部的n－1个盘按要求移到柱B上，共搬动了1na次；第二步，将柱A上的最大一个盘移到柱C上，只要搬动一次；第三步，再从柱B将n－1个盘按要求移到柱C上，也要用1na次。由加法法则，{an}的定解问题为1,1211aaann(3.1.3)例3.1.2（Lancaster战斗方程）两军打仗，每支军队在每天战斗结束时都清点人数，用a0和b0分别表示在战斗打响前第一支和第二支军队的人数，用an和bn分别表示第一支和第二支军队在第n天战斗结束时的人数，那么，an－1－an就表示第一支军队在第n天战斗中损失的人数，同样，bn－1－bn表示第二支军队在第n天战斗中损失的人数。假设一支军队所减少的人数与另一支军队在每天战斗开始前的人数成比例，因而有常数A和B，使得1111nnnnnnBabbAbaa其中常量A、B是度量每支军队的武器系数，将上述等式改写成1111nnnnnnBabbAbaa(3.1.4)这是一个含有两个未知量的一阶线性递归关系组。例3.1.3设20nkknrkkna，求{an}所满足的递推关系。（解）分两种情况：当n为偶数时，令n＝2m，则21n＝22n＝m－1于是an可写成an＝mkkrkkm02＝02m＋112mkkrkkm＋mrmm＝02m＋1112mkkrkkm＋11112mkkrkkm＋mrmm上式右端前两项之和为121010111121202nnkkmkkmkkarkknrkkmrkkmm而后两项之和为2022mjjrjjmr＋111mrmmr＝1022mjjrjjmr＝2202njjrjjnr＝2nra于是得na＝1na＋2nra当n为奇数时，同样可证上述递推关系成立。因此，所满足的递推关系是na＝1na＋2nra，n≥2另外，显然有a0＝a1＝1。例3.1.4设0出现偶数次的n位八进制数共有na个，0出现奇数次的数共有nb个。求na和nb满足的递推关系。对0出现偶数次的n位八进制数分两种情况讨论：（1）最高位是0，则其余n－1位应该含有奇数个0，这类八进制数共有1nb个。（2）最高位不是0，则其余n－1位还应该含有偶数个0，这类八进制数共有71na个。因此有na＝71na＋1nb。同理可得nb＝1na＋71nb，所以na、nb满足1777111111baabbbaannnnnn,,,例n＝20出现偶数次的数00，11，12，13，14，15，⋯，77，共50个0出现奇数次的数01，10，02，20，03，30，⋯，70，共14个例3.1.5用后退的Euler公式求常微分方程10yyxyy,的...