归纳法：算法证明与动态编程思想

       本人最近在读TAOCP,虽感丛书内容浩繁，难以在有限时间内研读，但亦收获颇丰。本文是在读过“1.2.1 数学归纳法”（后文的“本篇”均指TAOCP 1.2.1）之后的思考，也包含本篇的关键内容，以供复习参考。

数学归纳法与广义归纳法

       本篇是从数学归纳法开始的。稍有数学基础的人都明白数学归纳法的内容：

假定需要证明P(n)对所有正整数n为真，那么可以：

(1) 证明P(1)为真
(2) 证明“如果P(1),P(2),......,P(n)全部为真，那么P(n+1)也为真”，这个证明应对任何正整数成立

       很容易看出，使用数学归纳法证明可以看成是一个输出“P(n)为真”的程序/算法：

E1: k<-1，输出P(1)的证明
E2: 如果k=n，那么结果已经输出
E3: 输出“因为已经证明了P(1),P(2),......,P(k)，所以P(k+1)为真”
E4: k<-k+1，跳转到E2

       那么我们为什么可以使用这样的归纳思想与归纳法呢？虽然上面的算法看起来已经很简明、正确，但是显然数学归纳法涉及到了无穷的概念，我们是否需要证明数学归纳法的正确性呢？实际上数学归纳法的思想是将P(n)的正确性与正整数n的定义绑定，而正整数的定义天生就是归纳的，我们认为正整数的归纳定义是一种公理化的定义，无需证明，因此证明方式与正整数定义如出一辙的数学归纳法也无需证明。
       在证明一些难以表示为P(n)这样仅与一个正整数变量有关，而至少要表示成P(p,q)这样含有多个正整数变量的命题时，上面的数学归纳法就显得力不从心。有的方法会曲线救国：先证明P(1,1)，再证明“P(1,1),P(2,1),......,P(p,1)为真可证明P(p+1,1)”与“P(p,1),P(p,2),......,P(p,q)为真可以证明P(p,q+1)”这两条命题，分两步得出结果。这不失为一个解决方案，但它没有摸到归纳法的精髓。
       虽然数学归纳法作为一种古老的方法，依赖的是正整数的公理化归纳定义，但由它发展而来的广义归纳法则是使用了集合与关系的理论，不仅能支持证明P(p,q),P(p,q,s)这样的与正整数有关的命题，还扩充了命题自变量的范围。
通过思考数学归纳法，我们可以朴素地将其思想总结为这样：

如果我们能够：
(1) 证明：“最开始”的命题；
(2) 证明：如果“所有排在前面”的命题都已经被证明，可以通过这些命题证明本命题。
那么就能证明这个命题“序列”里的任意一个命题。

       经过总结，我们可以提出在任意集合上的“良序”关系，借助这个关系，达到归纳证明的目的，不管集合的元素是不是同一类、是不是可数。

集合S上的良序关系@具备以下性质：
(i) 传递性
(ii) 任意S上的x、y，三种可能性：x@y，y@x，x=y恰有一种成立
(iii) 对S的任意非空子集A，A上存在元素x，使得A的任意元素y，都有x@y或x=y

       广义归纳法推广归纳法，在上面良序关系的基础上说明了：如果在P(y)对于所有x@y均为真的假定下能够证明P(x)，那么P(x)对S中的所有x为真。

       对于从良序关系的定义，我们可以看到一点“朴素”的归纳法思想：(i)与(ii)保障了集合元素上有全序，我们可以构建“所有排在前面的命题”的列表用于证明当前命题；(iii)保障了“最开始的命题”的存在。显然，正整数集上的“小于”关系就是良序关系。类似地，如果我们能够对字符集合S定义一个良序关系_{，那么就可以对等长字符串集合T_n（包含所有用来自S的字符构成的长为n的字符串）也定义一个良序}：如果存在k (1 <= k <= n)使x_j=y_j对于1 <= j < k 恒成立,而x_{ky_k，那么在T_n上(x₁,x₂,...,_n)}(y₁,y₂,...,y_n).

归纳法成果：算法正确性证明

       许多算法包括分支、循环结构，应该如何使用有限的证明篇幅说明可能执行任意次分支、循环的算法的正确性呢？再复杂的算法也可以用流程图表示它的有限个分支、循环步骤，利用广义归纳法，我们可以找出每一个步骤之前的前提/断言/不变量，然后证明经过这个步骤之后，后续步骤的前提/断言/不变量是正确的。这要求在流程图中：

如果指向某方框的至少一个箭头上的断言在执行方框内操作之前为真，那么离开该方框的相关箭头上的所有断言在执行方框内操作之后都为真。

       这样一来，我们就可以用归纳的方法，说明在算法每一个步骤（方框）前的断言都为真，也就包括“算法终止”的步骤，保证了算法终止时结论的正确性。

归纳思想成果：动态编程

       动态编程思想主要是：存储可重用的中间计算结果；使用较小规模的计算问题答案扩展到较大规模的问题计算。这便应用了归纳思想。在经典的“曼哈顿地图路径”问题中，动态编程将输入慢慢从(2,2)扩展到(m,n)，实际上就是手动执行归纳的每一步。在现实的大部分问题中，解题使用(1,1)->(1,n),(m,1)->(m,n)的手段较多，并不会真正定义严格的良序并使用广义归纳法。但是，如果要解决与字符串有关的问题，可以应用前文所提的良序定义与广义归纳法，使算法正确性更加容易证明。