组合数学幻灯片54迭代法与归纳法

§5.4迭代法与归纳法在§5.2，§5.3节中，我们已经讨论了k阶常系数线性齐次递归关系的一般解法和k阶常系数线性非齐次递归关系在f(n)为某些特殊形式的一般解法。这些解法总的说来是依赖于能求出k阶常系数线性齐次递归关系的特征根。但是，当k较大时，k阶线性齐次递归关系的特征方程的次数就较高，这就面临着解高次方程的困难以及求解满足初值条件所得到的具有k个未知数的k个线性方程组的困难。另外，对于非线性递归关系和非常系数线性递归关系，还没有给出一种求解的方法。这样一来，就更有必要讨论求解递归关系的其他方法。本节将用几个例子来讨论求解递归关系的另外两种方法，这就是迭代法和归纳法。解：递归关系式(5.3)是常系数线性非齐次递归关系，可以用§5.3节中的方法求解。这里，我们用另一种称之为迭代的方法求解。1)1(01annaann求解递归关系式(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)是一个非常系数线性递归关系。下面用迭代法求解。1)2()64(11ananann求解递归关系反复利用递归关系式(5.25)进行迭代有an=(4n-6)an-1=(4n-6)［4(n-1)-6］an-2=(4n-6)(4n-10)an-2=(4n-6)(4n-10)［4(n-2)-6］an-3=(4n-6)(4n-10)(4n-14)an-3………………=(4n-6)(4n-10)(4n-14)…6·2·a11232)72(2)52(2)32(2nnn)]32)(52)(72(531[21nnnn)22)(42)(62(642)!22(21nnnnn)!1()!22(nn122)!1(nnn解：递归关系式(5.26)是一个非线性递归关系。反复利用递归关系式(5.26)进行迭代有2)1(120212anaann12212nnaa1)12(222na122222na12)12(2232na求解递归关系如果an0，则有12222233na01212022222nna1224nn125n125nna注意，递归关系式(5.26)还可以作一个变换变成一个常系数线性非齐次递归关系。然后利用§5.3节中的方法求解。作一个什么变换，请读者自己考虑.解：式(5.10)实际上是§5.1节中例4所导出的递归关系。在§5.3节中已经求出式(5.10)的解，下面我们用另一种方法求解式(5.10)。这个方法就是归纳法。2)2()1(211annaann求解递归关系式(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一样，先求前几项的值0)1(031annaann4)11(11122301aa4)12(29222312aa4)13(336322323aa求解递归关系然后，用归纳法证明以上猜想是正确的。n=0,1,2,3,结论显然成立。4)1(22nnan于是，我们猜想式(5.27)的解的一般公式为则当n=k+1时，有4)1(22kkak32231)1(4)1()1(kkkkaakk4)2()1(4)44()1(2222kkkkk设n=k时，结论成立。即有可见，当n=k+1时，结论仍然成立。•总结：•1迭代法的特点：迭代展开，简化迭代式；•2归纳法：（1）求出前几个值，并观察其规律，猜想出an的表达式；（2）用数学归纳法证明猜想出an。•3这些方法常是交叉使用，要看哪些更简单。