数列及递推关系.doc

3 数列的递推关系对于数列 ,若当 时, 之间满足函数关系1na1k12,,nnnkaa与2(,)0nkF (1)或 1,nnf 2则称 或 为 阶递推关系或 阶递归关系.由此递推关系及初值条件 所确(1)2kk 12,ka定的数列称为 阶递推数列.在 阶递推关系 中,我们规定每一项的次数为该项中()的次数的和,该项的系数为这项中除 之外其余 的12,,nnnkaa 12,,nnnka因数.在 阶递推关系 中,若各项的系数均是与 无关的常数,则称这个递推关系为常系数(1)递推关系；若递推关系中各项的次数相同,则称这个递推关系为齐次递推关系；若递推关系中各项的次数均不超过一次,则称这个递推关系为线性递推关系.例如,是常系数递推关系. 是二2130(2)nna3253120()nnnaa阶齐次递推关系. 是二阶线性递推关系；21()na是 3 阶常系数线性齐次递推关系.下面我们介绍递推关系中1234()nn常见的一些求解方法.基本原理定理 设 是已知数列,对于关于 的一阶递推关系,()gna（叠加法）若 ,则(1)1()2nag12();nkga（累乘法）若 ,则 ；(2)1()n12()nka（不动点法）若 得不动点,则有31),nabcbpfxbc且 是.1()(2nnapb证 , 显然.因为 的不动点,所以 ,又 ,两式相减得(3)()fx是 pbc1nabc.1nnapb对于常系数线性齐次递推关系120nnknabab (3)其中 ,我们称方程0kb121kkkkxxx (4)为递推关系 的特征方程.特征方程 的根称为递推关系的特征根.若 为特征方程(3)(3) 0x的 重根,我们将 个数列 称为递推关系 的由特征根 所(4)rr100,,nrnxx (3)0x确定的 个特解.有了这些约定,对于常系数线性齐次递推关系,我们有如下结论：定理 设 分别为特征方程 的 重根, 重根, 重根,则递推关系212,s (4)1r2sr的通解为(3) 121212 112,srnnnrrnnnssacxcxcxcx 其中 为任意常数,即递推关系 的通解为各个特征根所确定的特解(,)ij ijr(3)的线性组合.定理 的证明见组合数学教材.由定理 知，对于常系数线性齐次递推关系，只要能求22出特征方程的特征根,就能求出这个递推关系的通解,在给定初值条件下,我们可用初值条件确定通解中的任意常数,进而求出满足初值条件的特解.一个数列常常可能满足多个递推关系,对于分式递推关系1(2)nabcd (5)其中 ,我们希望找到两个常数 使得能将 化成如下形式0db,pq(5)（6）1nnapkq下面我们讨论 应满足的条件.,因为 ,所以,1 111()()n nn nnb bpdpaapcdacbpdcc  要将 化为 ,只需(5)6 bpdac (7)q (8)由 得 (7)apbcd (9)由 得 (8)q (10)令 表明 是 的不动点,这就说明了若函数 有,(9)10axbfcd,p()fx()axbfcd两个不动点 ,则递推关系 可化为递推关系 .pq(5)6如果 只有一个不动点,同样可证明递推关系 可化为如下形式：()xfc(5)1(2)nnkap这样我们得到如下结论：定理 设 , ,若函数 有两个不动点 ,则分式递推关30dbc()axbfcd()fxpq系 12na()可化成 .1()nnpkq若函数 只有一个不动点 ,则递推关系 可化成 .()fxp()1(2)nnkap方法解读3对于某些递推关系,我们可用定理 至定理 中的叠加法,累乘法,不动点法,特征根法求13解,也可以先猜测数列的一般项,然后再用数学归纳法证明.除这些方法外,我们常常是通过代换及代数恒等变形,将一个不熟悉的递推关系转化成一个可求解的递推关系,在作代换与变形时,常用的化归思想有如下几种.（1）无理化有理：当递推关系中含有无理式时,通过代换与变形化去递推关系中的无理式.多元化少元：当递推关系中所含的未知数列有多个时,通过消元化成只含有一个未(2)知数列的递推关系.高次化低次：当递推关系的次数较高时,通过变形与代换降低递推关系的次数.(3)高阶化低阶：当递推关系的阶较高时,通过代换与变形,降低递推关系的阶.(4)非线性化线性：对于一个非线性递推关系关,若能把它化为线性递推关系,就先作这5种化归.非齐次化齐次：一个非齐次的递推关系,利用代换、消元的思想把它化为齐次递推(6)关系.需要说明的是,一个数列所满足的递推关系常常不是唯一的,因此,对于一个较为复杂的递推关系,我们可猜测满足这个递推关系的数列也满足某一个较为简单的递推关系,在证明了我们的猜想之后,通过简单递推关系的求解去寻求原问题的答案.例 在正项数列中,已知 ,求这个数列的通项.13110,nnaa解 ,则有 .lg2lg,l3nnab令 2b解方程 ,得 ,由定理 知 可化为 ,得xx()13()nnb.13())nnb， ，1lg2a11()23()nnb.13()0nnb例 已知 时,1,4当12()6nnabb求 ,.n解 由 得, ,从而有 ,代入 ,得(2)16na1216nnab()5nbb (3)的特征方程为 ,从而知特征根为 ,所以 的通解为(3)20x12,3x().123nnc1214,646bab12,93.c解之得 ，128,3c.nnnb将 代入 ,得 .()148nna例 已知 ,求 .311 2,,na当 时 n解 解方程 122,,,xx得111112 2(23)2nn nnnnaaa从而有 1(3)(23).2nnnaa解之得 [].1()nn例 已知正数数列 满足4na212113nnna (1)且 ,求 的通项公式.12,3an解 两边同除以 ,得 ()1na21132nnaa(2)令 ,则由 可得 .1nnb(2)1nb解方程 从而有 ，3,,xx得 13()nnb.1()nb, .211a13,1,nb13na2(3),nn再由累乘法知 .12(3)nkka例 已知 为数列, 当 时,有5n14,n, 21 168()2naaa(1)求 .n解 由 得()2111)68(),nnn218)0,naa(4)0,从而有 . .1n14na解方程 所以,2xx得 1(2)(),nna12()),nna.例 已知 满足 时,有6n12,a当 n12n (1)求 .na解 由 得 (1)11nna (2)得()2,21142,nna1452nn3na (3)的特征方程为 (3)32,x 4的 个根分别为 所以 的通解为4123,1()123.nnacc因为 ,所以 解方程组12a3a123,48,c得 123,cc.na注：本题是用通法求解.若将 变形为 并令(1)211()()2,nnnaa,则解法会简单一些.1nnb例 已知 满足 当 时,有 7na123,,an1123nna()求 .n解 由 得 (2)312nnaa (3)得()3，12312nnnna，123a.11()()nnn,两边同除以 ,得0na2na1132,nna或1133122,nn 1423,na从而有 即1,nna1.na利用特征方程的特征根,易得 5235235()().nnn 例 已知 时,81,a当(42),6nnna(1)求 .解 令 ,则有 从而有124nnba21,4nb2211(4),6nnbb化简得 21469,nn221()(3).nn又因为 所以 ,0,b13b13()2nn1,115,()2nnb2213,nnb23.4na例 数列 满足 时, 9n16,an当 2153[1]4nnnaa(1)这里 表示 的整数部分,求[]x.解 猜想 12346,,,a12.n (2)下证 成立.()当 时, 显然成立,假设对于 成立,那么当 时,n() ()k时 1k，2111 15324kkk kaa 2111[],kkk即 所以对于 时 也成立.由归纳法原理知 成立.21kka， n(2)(2)由 得()2(),na115n15.na例 设整数数列 满足 当 时,有0n12,7,2na(1)试求 的通项公式.na分析 当 给定时,满足 式的整数 是唯一的,所以 式也给定了数列1na(1)2na(1)所满足的一个递推关系.为了找到 所满足的其它递推关系,可猜测 满足一个二nan na阶常系数线性齐次递推关系 然后利用 式求出 再用21nAaB(1)3425,89,的值求出 ,最后证明 1234, 3,23,nna(3)解 我们用数学归纳法证明：当 时, 式成立.()当 时,因为 由 得 ,所以 式成立.n12,7,a135,72()假设对于 时 成立,那么当 时,因为k(3)nk2 2 221 1 12 211(()()3kkkkk kkkkaaaa  2212111(3) .kkkkkka 从而有 ,即对于 , 式成立.由归纳法原理知结论成立.32kkkn(3)递推关系 的特征方程为 ,特征根为 ,所以()20x1237317,xx的通解为(3)1237317()().nnnacc由 得12,,1255,,68687537173()().68nnna习题 3已知 为整数数列, 当 时, 求2.n12,0,a231,na.na在数列 中,已知 当 时, ,求3.nb1,b341nba.n已知 为正数数列, 时, 求 .5.na01,2an当 221,nnna。