组合数学幻灯片54迭代法与归纳法ppt课件.ppt

在5.2，5.3节中，我们已经讨论了k阶常系数线性齐次递归关系的一般解法和k阶常系数线性非齐次递归常系数线性非齐次递归关系关系在f(n)为某些特殊形式的一般解法。这些解法总的说来是依赖于能求出k阶常系数线性齐次递归关系的特征根。但是，当k较大时，k阶线性齐次递归关系线性齐次递归关系的特征方程的次数就较高，这就面临着解高次方程的困难以及求解满足初值条件所得到的具有k个未知数的k个线性方程组的困难。另外，对于非线性递归关系和非常系数线性递归关系，还没有给出一种求解的方法。这样一来，就更有必要讨论求解递归关系的其他方法。本节将用几个例子来讨论求解递归关系的另外两种方法，这就是迭代法迭代法和和归纳法归纳法。解：解：递归关系式(5.3)是常系数线性非齐次递归关系，可以用5.3节中的方法求解。这里，这里，我们用另一种称之为迭代迭代的方法求解。求解递归关系式(5.3)反复应用递归关系式(5.3)进行迭代有 an=an-1+n =an-2+(n-1)+n =an-3+(n-2)+(n-1)+n =a0+1+2+3+(n-1)+n =1+n(n+1)/2 =(n2+n+2)/2解解：递归关系式(5.25)是一个非常系数线性递归关系。下面用迭代法求解。求解递归关系反复利用递归关系式(5.25)进行迭代有 a an n=(4n-6)a=(4n-6)an-1n-1 =(4n-6)=(4n-6)4(n-1)-64(n-1)-6a an-2n-2=(4n-6)(4n-10)a=(4n-6)(4n-10)an-2n-2 =(4n-6)(4n-10)=(4n-6)(4n-10)4(n-2)-64(n-2)-6a an-3n-3=(4n-6)(4n-10)(4n-14)a=(4n-6)(4n-10)(4n-14)an-3n-3 =(4n-6)(4n-10)(4n-14)=(4n-6)(4n-10)(4n-14)6 62 2a a1 1解解：递归关系式(5.26)是一个非线性递归关系。反复利用递归关系式(5.26)进行迭代有求解递归关系如果如果 an0，则则有 注意，递归关系式(5.26)还可以作一个变换变成一个常系数线性非齐次递归关系。然后利用5.3节中的方法求解。作一个什么变换，请读者自己考虑作一个什么变换，请读者自己考虑 .解解：式(5.10)实际上是5.1节中例4所导出的递归关系。在5.3节中已经求出式(5.10)的解，下面我们用另一种方法求解式(5.10)。这个方法就是归纳法。归纳法。求解递归关系式(5.10)先用初值条件a1=2求出前几项，并观察其规律。a a2 2=a=a1 1+2(2-1)=4(=2+2(2-1)=4(=22 2-2+2)-2+2)a a3 3=a=a2 2+2(3-1)=8(=3+2(3-1)=8(=32 2-3+2)-3+2)a a4 4=a=a3 3+2(4-1)=14(=4+2(4-1)=14(=42 2-4+2)-4+2)a5=a4+2(5-1)=22(=52-5+2)由上面所得到的值，我们可以猜想式(5.10)的解的一般公式为 a an n=n=n2 2-n+2-n+2为了证实上述猜想为了证实上述猜想a an n=n=n2 2-n+2-n+2确实是式确实是式 (5.10)(5.10)的解，我们用归纳法证之的解，我们用归纳法证之由上面计算前几项的值，显然，对于n=1,2,3,4,5时，结论是成立的。设n=k时，结论成立。即有 a ak k=k=k2 2-k+2-k+2 则当n=k+1时，有 a ak+1k+1=a=ak k+2(k+1-1)=k+2(k+1-1)=k2 2-k+2+2k-k+2+2k =(k+1)=(k+1)2 2-(k+1)+2-(k+1)+2 可见，当n=k+1时，结论也是成立的。解：解：与例4一样，先求前几项的值求解递归关系然后，用归纳法证明以上猜想是正确的。对于n=0,1,2,3,结论显然成立。于是，我们猜想式(5.27)的解的一般公式为 则当n=k+1时，有设n=k时，结论成立。即有可见，当可见，当n=k+1n=k+1时，结论仍然成立。时，结论仍然成立。总结：1 迭代法的特点：迭代展开，简化迭代式；2 归纳法：（1）求出前几个值，并观察其规律，猜想出an的表达式；（2）用数学归纳法证明猜想出an。3 这些方法常是交叉使用，要看哪些更简单。