第四节-用迭代法求解递推关系

§6.4用迭代法求解递推关系《组合数学》－Chapter6一个简单的递推关系，可以从方程出发，直接迭代出数列的通项公式，最后再使用归纳法证明所推导公式的正确性，这种求解递推关系的方法称为迭代归纳法.对某些非线性的递推关系,不存在求解的一般性公式,有时可考虑利用迭代归纳法去求解.例1求解递推关系3()(1),(0)0.fnfnnf解用迭代法解该递推关系,得333()(1)(2)(1)fnfnnfnnn33333333333(1)2(1)(0)12(1)12(1).fnnfnnnn利用归纳法可证明2233332(1)12(1)(12).4nnnnn因为f(0)=0=02,f(1)=13=12,f(2)=13+23=9=(1+2)2,f(3)=13+23+33=36=(1+2+3)2,所以,原递推关系的解为221()(1).4fnnn解递推关系常用的几种技巧.1.将非齐次递推关系齐次化例2求解递推关系1()2(1)4,(1)(1)3.nfnfnf解由递推关系可得2(1)2(2)4.(2)nfnfn(1)+(2)×(-4)得()6(1)8(2),(1)3,(2)10.fnfnfnff它的特征方程为2680,xx特征根为x1=2,x2=4于是通解为()24.nnfnAB代入初值f(1)=3,f(2)=10,求得1,2AB所以递推关系的解为1()(24).2nnfn2.将变系数的一阶线性递推关系化为常系数线性递推关系例3求解递推关系1()(1)1,2(0)1.nfnfnnf解令1121()()(),22(1)2(2)212nnnnnfnhnhnnnn代入上述递推关系并化简，即得到关于h(n)的递推关系2()(1),1(0)1.nhnhnnh解得02(),1knkhnk从而012(),21knnknfnk一般地，一阶线性递推关系可以表示成()()(1)()fncnfngn令()()(1)(1)(),fncncnchn则有()()(1),()(1)(1)gnhnhncncnc把变系数化为常系数.3.将一阶高次递推关系通过变量代换化为一阶线性递推关系例4求解递推关系2()3(1),(0)1.fnfnf解对该递推关系两边取自然对数，得ln()ln32ln(1).fnfn令h(n)=lnf(n),得()2(1)ln3.(0)0.hnhnh解得h(n)=(2n-1)ln3,从而21()3.nfnP1697(1)(2),8(2)