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

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