第四节用迭代法求解递推关系ppt课件.ppt

6.4 用迭代法求解递推关系,组合数学 Chapter 6,一个简单的递推关系，可以从方程出发，直接迭代出数列的通项公式，最后再使用归纳法证明所推导公式的正确性，这种求解递推关系的方法称为迭代归纳法.,对某些非线性的递推关系,不存在求解的一般性公式,有时可考虑利用迭代归纳法去求解.,例1 求解递推关系,解 用迭代法解该递推关系,得,利用归纳法可证明,因为 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,所以,原递推关系的解为,解递推关系常用的几种技巧.,1.将非齐次递推关系齐次化,例2 求解递推关系,解 由递推关系可得,(1)+(2)(-4)得,它的特征方程为,特征根为 x1=2, x2=4,于是通解为,代入初值f(1)=3,f(2)=10,求得,所以递推关系的解为,2. 将变系数的一阶线性递推关系化为常系数线性递推关系,例3 求解递推关系,解 令,代入上述递推关系并化简，即得到关于h(n)的递推关系,解得,从而,一般地，一阶线性递推关系可以表示成,令,则有,把变系数化为常系数.,3. 将一阶高次递推关系通过变量代换化为一阶线性递推关系,例4 求解递推关系,解 对该递推关系两边取自然对数，得,令 h(n)=lnf(n), 得,解得 h(n)=(2n-1)ln3,从而,作业：,P169 7(1)(2) ,8(2),