数学归纳法到底是什么样子的？ | 在B站学数学笔记（一）

数学归纳法，可以用来证明一个“序列”中的每一个“元素”都具有某种“性质”。方法分两步：

一、证明“序列”中的第1个“元素”具有这一“性质”；

二、证明当任一“元素”（第n个）具有这一“性质”时，它的“后继”（第n+1个）必然具有这一“性质”。

完成了这两步，就已经证明了：这一“序列”中的每一个“元素”都具有这一“性质”。

以上，只是示意性的描述，并非严格定义。

这里提供应用数学归纳法的三个简单例子。

1、

求证：

如图，任何一个边长为2n的正方网格，里面挖掉任一小方格；这样的图形，必然能被下面的L形砖块填满。

证明：

一、当n=1时，显然，无论挖掉哪个小方格，剩下的图形立刻能用L形砖块填满。

下一步，只需证明，当待证的性质在边长为2n的网格中成立，那么在边长为2n+1的网格中它必然成立，即可。

二、假定待证的性质在边长为2n的网格（图中“示意”为4×4网格）中成立，那么面对边长为2n+1的网格，我们可以把它划分成四个象限。需要挖掉的小方格在哪个象限，我们就可以用一块已经被L形砖块填满的边长为2n的网格填上它；另外三个象限，我们可以如图安排：各挖掉一个角上小方格，用三块如此完成的边长为2n的网格填上，最后用一块L形砖填上最后的缺口。

显然，当边长为2n的网格具有这一性质时，边长为2n+1的网格必然具有这一性质。

得证。

2、

“汉诺塔”问题。

如图：有三根柱子，在一根柱子上，按从小到大的顺序叠放着若干枚圆片。现在，我们可以按这样的规则把圆片移动到别的柱子上：每次只能移动一枚，并且在任一柱子上，大圆片不能摆在小圆片上面。

求证：

把n枚圆片移动到另一根柱子上，需要的最少移动次数是2n-1。

证明：

一、当n=1时，移动1次即可，显然成立。

二、假定把n枚圆片移动到另一根柱子上，需要移动2n-1次；那么当这n枚底下又多了一枚，我们需要做的是：先移动2n-1次，把上面n枚移到第二根柱子上；再花费1次，把最大的一枚移到第三根柱子上；最后花费2n-1次，把n枚从第二根柱子移到第三根柱子。所以，移动n+1枚圆片，总共需要的次数是：

2n-1+1+2n-1=2n+1-1

得证。

从这个例子我们可以看出，数学归纳法或许难以帮我们“发现”公式，但是“验证”公式，数学归纳法是一把好手。

3、

一个圆，被任意多条线段，划分为N个区域。

求证：

只需用两种颜色，给不同的区域着色，就足以使任何两个共享一条边的区域拥有不同的颜色。

证明：

一、当线段数n=1时，显然成立。

二、假定线段数为n时，两种颜色能满足我们的需求；那么我们在此基础上增加一条线段：

然后在线段的一边（比如左边），把两种颜色互换：

我们看到，共享边不是新加线段的一部分的相邻区域，颜色区分不会受影响；而共享边刚好是新加线段的一部分的相邻区域，刚好因为“颜色互换”，实现了区分。

所以，只要这一性质在线段数为n时成立，那么它在线段数为n+1时，必然成立。

得证。

数学归纳法的“视觉化”：多米诺骨牌。

证明步骤一，相当于说第一块骨牌会被推倒；

证明步骤二，相当于说任何相邻骨牌都足够接近，使得一块推倒以后另一块必然会倒。如此，就能推出：所有的骨牌都会倒。

这个视觉意象，有助于我们“看到”数学归纳法适用的是怎样的“序列”。至于严格的定义，就不是本篇的事了。

- END -

公众号【小李飞刀读古龙】