第二章总结

2.1

原始的数学归纳法可以变形为各种形式，核心是有几个知道的n比较小的值或者性质+有一些从前向后的推断方式，然后推出一系列东西。比较常见的变形有强归纳法、间隔归纳法（n=1,2,..k时成立，n-k成立能推出n成立）、指数归纳法（n/k推n），等等。关键：根据我们掌握了什么决定使用什么样的变形。

2.2

要求一串运算式子的含n表达式但猜不到表达式时，如果知道表达式大致的形式（比如是n的三次多项式或者形如AXlogn+n^2XB+C），可以直接待定系数用前几个结果求出待证明的表达式，然后证明。

2.3

“一般位置”的例子：关键有两点，一个是“隐去一条线使得n-1的结论可用”，一个是“增加该条隐去的线对比增加该线前对区域分割造成的影响”。这里作者省略了一个分类讨论的过程：在对比影响时，有三类区域———“被隐去过的线”和“第n+1条线”都没经过的区别、有一条其中的线经过的区域和两天线相交的区域。只有最后一种区域才会在隐去和不隐去该线这两种情况下对“添加第n+1条线”的操作产生不同反馈（不隐去比隐去多增加了一个区域）。
归纳法可以多次使用，例如先证明增长率（递推关系）再证明式子的和（结果）。【1】

2.4

关键是根据公共边是否是新增的直线进行讨论。如果不是的话，保留原色的部分无影响，颜色反转的部分由于总共只有两种颜色也无影响；如果是的话，原本颜色一致——以新增边为公共边说明被新增边切割了，左右一个不变一个反转后刚好颜色不同。

2.5

和【1】类似，递推关系就是两行之和的差。
从结果出发得知需要推什么，逆向思考很常用。

2.6

虽然等比求和就能解决，但这里“整体右移”的思路很巧妙。提出来一个1/2后，原本的第2到n+1项变成了新的1到n项。这种针对整体的灵活处理核心是往n-1假设上靠，把整体变得可以利用这个假设。

2.7

这里的核心是先证明多参中某个参数X为基础值（例如1）时结论成立——该结论在此时本身又需要一次数学归纳证明，然后针对X进行数学归纳。有几点比较关键：

1）

F=1时只有一个面，此时必无回路，问题转化为树的性质

2）

作者省略的关于“无向连通图（树）所有节点至少与2条边相连则一定存在回路”的可能的证明：假设节点A分别和节点BC（BC不同）相连，则由A经过B一定可以到达C——因为B和C连通，C再到A，形成回路

3）

既然存在至少一个节点边数小于2，如果边数是0的话就不连通了，所以该节点边数必为1（叶子节点）

4）

在基础假设的证明中，想象出来的n+1个节点的情况是“自由”的——或者说是“随机”的（相当于针对任意情况），但我们选中好叶子节点并砍掉后剩下的n个节点就缩减为“固定”的特定情况，该特定情况必符合广泛的结论（n的结论）。这样保证了对任意情况的可适性。

5）

在基础假设的证明中，也可以换以一种和作者不同的可能证明方式——先想象n个节点的任意某种场景然后再任意添加符合要求的节点生成第n+1个节点的场景，添加完新节点后必须增加一条该节点和某已有节点的边且只能增加这条边。因为如果不加这条边，新节点被孤立，不符合连通；如果增加了两原始节点之间的边，由连通性可知构成回路，不符合要求；如果多增加了一条新节点和原始节点的边，由类似2）的证明可知也构成了回路。因此边数和节点都一定各自加一。证毕。
作者说选择不同的（参数？）顺序进行归纳证明的难度可能大相径庭，例子在后面章节。
【待解决】
P10的任意一张平面图都可以用4种颜色有效着色的数学证明
自己到自己的边（自环？）会造成什么影响

2.8

很重要的一个思想：当情景很乱很随机的时候，如何找到合适的切割方式把n和第n+1个或者把前面一大堆和新加入的一小部分分开？这个例子告诉我们可以随机寻找一个点，然后把该点和它的外指向点作为一个整体处理。在之前的题目中，找过叶子节点作为特殊节点。在之后的题目中，也可能寻找具备特殊性质的一对点或属于某特定集合的一个随机点——总之，当没有头绪的时候，不妨对存在的东西（在图里面就是点或者边）进行分类：哪个集合是特殊的（例如本例的独立性），哪个是普通的，哪些点具有特定性质（比如叶子节点），哪些点没有这些性质。从中选择可能的单元单拎出来，然后对剩下的大部分东西使用归纳假设，一种选择不行就换一种，可能试着试着就出来了，至少比毫无头绪要好。

2.9

感觉作者有点把问题描述的复杂化了，翻译的也有点点小问题。大概就是讲了两种从小到大拓展（拼接）格雷码的方式（图片很清晰）——一种是线性增加，一种是2的指数倍增加。关键有两个，一个是往格雷码前面加0或者1比较巧妙，一个是奇数个格雷码不是开环吗，这个开环不要紧，在具体拼接时看图可知开路没有影响。稍微注意一下从小凑大大是2k+1（奇数）时，如果k恰好是临近的2的幂，最后位数不够了要取上限。例如2X3+1=7，3位数够了但是2X4+1=9需要有四位数。这都是细节问题，主要就是拼接思想，可以从中看到如何从小到大生成格雷码。感觉可能的拓展应用是不止两个一拼，还可以三四五六个一拼，线性增加的环也可以有多个。

2.10

【重要思想】定一个新的假设P，该假设的限制条件比原假设Q少——也就是更通用一些，然后证明P，再用P推出Q（因为Q属于P）。貌似证明会更难，其实可能变简单，例如本例。本例主要是连通性的限制反而让删边变得麻烦。
注意，定理2.12的意思是存在这样的节点对集合满足要求，不是对任意的节点对集合都满足要求。以及在证明加强版假设时用到了子图连通则必有偶数个节点的性质，整体的证明思路是隐去一个节点对和相应的路然后添加上去，和之前的平面区域划分（一般直线）有类似之处。

2.11

【重要】新的无限子集+n推n-1的归纳法形式（逆向归纳法）很有用。这个小节给出了如何构建满足要求的无限子集的例子。里面涉及到的技巧主要是整体设元后变换，其中对于无限子集的证明本身又用了一次数学归纳法（指数形式的归纳法）。

2.12

这就是数理逻辑当时讲过的内容——循环不变量，这个思想在证明循环正确性上很有用：在循环开始时假设成立、第K次循环成立推第K+1次循环成立、循环终止时能推得算法正确。思维混乱时记住”循环开始“和”循环结束“这两个节点可以有效缕清思路。
【疑问】

1、

独立和相邻的理解是否有误，相邻对于入和出应该有一个即可？

2、

迭代的有没有类似循环不变量这样的方便证明的东西？【重要】