第一数学归纳法：施塔特中心的地板砖

相关：

第一数学归纳法 vs 第二数学归纳法 vs 良序定理

第二数学归纳法：硬币问题和堆垛游戏

第一数学归纳法：施塔特中心的地板砖

良序原理：算术基本定理的证明

*数学归纳法是一种显示（局部）自然数元素都具有某种性质的有力工具。在离散数学和计算机科学中它都起到了重要作用。事实上，它的使用本身就是对离散性质的一种定义。归纳法的缺点在于它无法告诉你“究竟发生了什么”，即性质成立的根本原因，不过这也是它的一个优点，降低了证明的复杂性。*

在这篇博文和之后的博文中我会通过一些有意思的问题介绍数学归纳法中的第一数学归纳法和第二数学归纳法以及不变性原理（归纳法的一种，通常被用在step-by-step的推理过程中），并在最后总结良序原理、第一数学归纳法和第二数学归纳法的联系。

第一数学归纳法（Ordinary Induction）: 设P是对于非负整数的一个谓语，则

• P(0)成立
• 对于所有的非负整数n，P(n) -> p(n + 1)
• 则对于所有的非负整数m，P(m)成立

看起来这个方法非常简单，以至于我们可能找不到能证明它的正确性的公理（实际上它和良序原理是等价的）。用公式表示就是：

通常而言，使用第一数学归纳法都可以遵循下面这个模版：

1. 声明接下来的证明会采用归纳法。
2. 定义正确的谓词P，P(n)通常被称作“归纳假设”。归纳最后得到的结论就是对于所有非负整数p(n)均成立。一个清晰的归纳假设通常是归纳法中最重要的一步，所以不要简写！简单的情况下P就是你要证明的东西，但有些时候P可能会包含一些变量，这个时候就要说明清楚哪一个是n。
3. 证明P(0)成立。
4. 证明对于所有非负整数n，P(n) -> P(n + 1)。即假设P(n)成立，然后利用P(n)成立这个假设推出p(n + 1)也是成立的。要注意的是，我们必须保证P(n) -> P(n + 1)对于所有非负整数都是能够成立的，即“推理链条”不能被中断（本文最后会有一个反面例子）。
5. 由归纳法得出结论。

**施塔特中心的地板砖问题（应该是一个真实的事）： **

几年前MIT打算建一座名叫施塔特中心的建筑物，但是在建筑过程中发生了资金不足的情况。校董事会商议后决定邀请社会人士捐款，并为捐款最多的一位做一座雕像B立在大厅。这个建筑的设计师设计的大厅形状是一个由瓷砖铺成的长宽为2^n的正方形，而且采用的瓷砖也很特别，是一个由三个1 * 1正方形组成的L形瓷砖，如下图所示：

设计师还要求，雕像B只能立在大厅的正中心（对于n=0，整个大厅就是那一个雕像，其余的情况雕像必须放在中心的2 * 2的空间内），其中n = 2的情况如下图所示：

设计师的方案对于n的取值又要求吗？还是说对于任意非负整数n都能满足呢？

下面利用第一数学归纳法对其进行证明：

1. 本次证明采用数学第一归纳法
2. 设谓词P(n)为对于非负整数n，设计师的要求能够满足。
3. P(0)成立因为B雕像占据了整个大厅（不需要铺瓷砖）。
4. 假设P(n)成立，即对于一个2^n长宽的正方形，我们可以把B雕像放在中心位置，其余的部分铺上L形瓷砖。

这个时候问题发生了，我们不能由P(n)推出P(n + 1)，因为我们只能得到可以在2^(n + 1)的正方形中心的四个对角方向的“中心”可以放置B雕像。

当这种情况发生时，首先的想法应该是找一个更加普遍或者说强壮的归纳假设，也就是之前归纳假设的超集。例如在这题中，我们可以把P(n)变为对于一个2^n长宽的正方形，我们可以把B雕像放在其中的任意位置，其余的部分铺上L形瓷砖。

这看起来有些奇怪——“如果你证明不了A，那就证明比A更普遍的B”——但是在归纳法中确实是这样的，因为我们在推P(n + 1)的时候也可以获得更好的条件。当然，增强后的P(n)首先要是（至少感觉上）是正确的。下面就采用增强后的P来证明：

1. 本次证明采用数学第一归纳法

2. 设谓词P(n)为对于非负整数n，可以把B雕像放2^n正方形的任意位置，其余的部分铺上L形瓷砖。。

3. P(0)成立因为B雕像占据了整个大厅（不需要铺瓷砖）。

4. 假设P(n)成立，即对于一个2^n长宽的正方形，我们可以把B雕像放在其中的任意位置，其余的部分铺上L形瓷砖。那么对于P(n + 1)，即一个2^{(n+1)长宽的正方形，我们可以将其分为四个2}n的正方形，而对于其中的每个正方形，由于P(n)成立，我们将其中的三个正方形的对角的那个1*1正方形空出来，在2^{(n+1)的正方形中心形成一个L形，并铺上一块瓷砖，这个时候我们就可以在剩下的那个2}n的正方形中任意放置B雕像了，如下图所示：

   

   由于这三个2^{n的正方形选择是随机的，所以可以得出结论，即我们可以在2}(n+1)的正方形任意位置放置B雕像，其余部分铺上L形瓷砖。

5.由归纳法得出对于非负整数n，我们可以把B雕像放在一个2^n长宽的正方形中的任意位置，其余的部分铺上L形瓷砖。

所以我们当然也可以把雕像放在中心位置了。可以看到，我们不仅证明了一个更强的结论，还找到了实现这种结论的算法。

如前面所说，在进行p(n) -> p(n + 1)这步时，我们必须保证P(n) -> P(n + 1)对于所有非负整数都是能够成立的，即“推理链条”不能被中断。这里举出一个有名的反面教材，证明所有的马都是一种颜色：

1.本次证明使用第一数学归纳法。

2.设命题P(n)为对于任意n匹马（n>=1)，它们的颜色一样。

3.这个命题对n=1时成立，即，只有1匹马时，马的颜色只有一种。

4.假设这个命题对n成立，即假设任何n匹马都是一种颜色。那么当我们有n+1匹马时，不妨把它们编好号：

1, 2, 3……n, n+1 ，对其中（1、2……n）这些马，由我们的假设可以得到，它们都是同一种颜色；对（2、3……n、n+1）这些马，我们也可以得到它们是一种颜色；由于这两组中都有（2、3、……n）这些马，所以可以得到，这n+1种马都是同一种颜色。即P(n) -> p(n + 1)

5.得到所有的马颜色相同。

这个证明的错误来于推理的第二步：当n=1时，n+1=2，此时马的编号只有1、2，那么分的两组是（1）和（2）——它们没有交集，所以第二步的推论是错误的。数学归纳法第二步要求n→n+1过程对n=1，2，3……的数都成立，而上面的证明就好比多米诺骨牌的第一块和第二块之间间隔太大，推倒了第一块，但它不会推倒第二块。即使我们知道第二块倒下会推倒第三块等等，但这个过程早已在第一和第二块之间就中断了。

参考：

1. Mathematics for Computer Science
2. 数学归纳法