◎课前对话
老师：假设现在有一排多米诺骨牌。如何将它们全部推倒呢？
学生：这个简单！只要将它们排列成其中1 个一倒就能顺次带倒下一个的形状就行了。
老师：这样还不够喔！
学生：啊？为什么呢？
老师：因为还需要推倒第一个多米诺骨牌。
学生：那不是理所当然的嘛！
老师：正是！这样你就能理解数学归纳法的两个步骤了。
本章学习内容
本章我们要学习的是数学归纳法。数学归纳法是证明某断言对于0 以上的所有整数（0，1，2，3…）都成立的方法。整数0，1，2，3…有无穷个，但若使用数学归纳法，只需经过"2个步骤"，就能证明有关无穷的命题。
首先，我们以求出1 到100 之和为例介绍数学归纳法。接着会穿插几道思考题来看一下数学归纳法的具体实例。最后，我们会讨论数学归纳法和编程的关系，一起了解一下循环不变式。
高斯求和
思考题（存钱罐里的钱）
思考题（存钱罐里的钱）
在你面前有一个空存钱罐。
第1 天，往存钱罐里投入1 元。存钱罐中总金额为1 元。
第2 天，往存钱罐里投入2 元。存钱罐中总金额为1 + 2 = 3 元
第3 天，往存钱罐里投入3 元。存钱罐中总金额为1 + 2 + 3 = 6 元
第4 天，往存钱罐里投入4 元。存钱罐中总金额为1 + 2 + 3 + 4 = 10 元
那么，每天都这样往存钱罐里投入硬币的话，第100 天时的总金额为多少呢？
思考一下
本题要求算出第100 天时存钱罐的总金额。要求出第100 天的金额，只要计算1 + 2 + 3+ … + 100 的值就行了。那么，具体应如何计算呢？
一般来说，最先想到的肯定是机械地将它们逐个相加。1 加2，再加3，再加4，…再加99，再加100。只要这样加起来就能得出答案了吧。如果说笔算比较花时间的话，也可以使用计算器或编程来计算。
不过，德国数学家高斯在9 岁时遇到了同样的问题，却马上得出了答案。当时他既没用计算器也没用电脑。那么，他究竟是如何做到的呢？
小高斯的解答
小高斯是这么考虑的。
1 + 2 + 3 + …+ 100 顺次计算的结果和100 + 99 + 98 + …+ 1 逆向计算的结果应该是相等的。那么，就将这两串数字像下面那样纵向地相加。
如此一来，就变成了101 + 101 + 101 + …+ 101 那样100 个101 相加的结果。这样的计算就非常简单了。只要将101 乘以100 即可，结果为10100。不过10100 是要求的数的2 倍，因此还得除以2，答案为5050。
答案：5050 元。
讨论一下小高斯的解答
小高斯的方法可谓绝妙非凡!
为了便于大家理解，我们将高斯的方法用图来表示。求1 + 2 + 3 + …+ 100 的结果，相当于计算图4-1 所示的排列成阶梯型的瓷砖块数。
图4-1 将高斯的方法图形化
高斯则又做了一个一模一样的阶梯，并将两者合二为一，组成了一个长方形。
图4-2 将2个阶梯组合成1个长方形
由2 个阶梯组合而成的长方形，纵向有101 块瓷砖，横向有100 块瓷砖。因此，该长方形由101×100 = 10100 块瓷砖构成。而所求的瓷砖块数就是10100 的一半，即5050。
我们来说一说高斯的计算效率。使用他的方法不需要花费力气逐个相加。只要将两端的1 和100 相加，结果乘以100 再除以2 就行了。
现在，假设我们不是从1 加到100，而是从1 加到10000000000（100 亿）。这次我们就不能采用逐一相加的方法了。因为即使计算器1 秒能完成1 次加法计算，加到100 亿也得花300 年以上的时间。
不过，如果使用高斯的方法，那么从1 加到100 亿也只要1 次加法、1 次乘法、1 次除法运算即可完事。我们来实际计算一下。
高斯（Karl Friedrich Gauss, 1777 - 1855）后来成为了历史上著名的数学家。
归纳
高斯运用了以下等式。
这里，使用变量n，将"1 到100"归纳为"1 到n"。这样，上面的等式就变为如下形式
那么，这个等式对于0 以上的任意整数n 都成立吗？即n 为100、200，或者100 万、100 亿时该等式也都成立吗？如果成立的话，又如何来证明呢？
这种时候就要用到数学归纳法了。数学归纳法是证明"断言对于0 以上的所有整数n都成立"的方法。
学生："对于所有整数n"，总觉得这种说法别扭。
老师：别扭？
学生：会感觉头脑中充满了整数。
老师：那么，改为"对于任一整数n"怎么样？
学生：啊！那样感觉稍微舒服些。
老师：其实说的是一回事呢！
数学归纳法-- 如何征服无穷数列
本节，我们就来讨论一下数学归纳法的相关内容。首先，从"0 以上的整数的断言"开始学起，然后使用数学归纳法来证明高斯的断言 。
0以上的整数的断言
0 以上的整数n 的断言"，就是能够判定0，1，2…等各个整数为"真"或"假"的断言。这样说明或许难以理解，下面就举几个例子。.
● 例1
o 断言A (n ) ：n ×2 为偶数。
A(n)，即"n×2 为偶数"的断言。由于n 为0 时，0×2 = 0 为偶数，所以A(0) 为真。
A(1) 又怎么样呢？因为1×2 = 2 为偶数，所以A(1) 也为真。
那是否可以说断言A(n)，对于0 以上的所有整数n 都为真（对于0 以上的任意整数n都成立）呢？
对！可以这么说。因为0 以上的任意整数乘以2 的结果都为偶数，所以对于0 以上的所有整数，断言A(n) 都为真。
● 例2
o 断言B (n ) ：n ×3 为奇数
那么，断言B(n) 又将如何呢？该断言对于0 以上的所有整数n 都成立吗？
例如，假设n 为1，则断言B(1) 就是"1×3 为奇数"，这个结果为真。但不能说对于0以上的所有整数n，断言B(n) 都为真。因为假设n 为2，则n×3 的值为2×3 = 6。而6 是偶数，所以断言B(2) 不为真（为假）。
n = 2 是推翻"断言B(n) 对于0 以上的所有整数n 都成立"的反例。
● 其他例子
那么请思考一下，在下面4 个断言中，对于0 以上的所有整数n 都成立的有哪些。
o 断言C (n ) ：n +1 为 0 以上的整数。
o 断言D (n ) ：n -1 为 0 以上的整数。
o 断言E (n ) ：n ×2 为 0 以上的整数。
o 断言F (n ) ：n ÷2 为 0 以上的整数。
断言C(n)，对于0 以上的所有整数n 都成立。因为若n 为0 以上的整数，则n + 1 肯定是0 以上的整数。
断言D(n)，对于0 以上的所有整数n 不成立。例如，断言D(0) 为假。因为0 -1 = -1，不是0 以上的整数。n = 0 是唯一的反例。
断言E(n)，对于0 以上的所有整数n 都成立。
断言F(n)，对于0 以上的所有整数n 不成立。因为当n 为奇数时，n÷2 的结果不是整数。
高斯的断言
在讨论了" 0 以上的整数n 的断言"之后， 我们将话题转回高斯的断言。
可以使用下述有关n 的断言形式来表现高斯的观点。
o 断言G(n) ：0 到n 的整数之和为 。
接下来要证明的是，"G(n) 对于0 以上的所有整数n 都成立"。可以通过描画前面的阶梯状的图（图4-1）来证明，但是有人可能会有这样的疑问：0 以上的整数有0, 1, 2, 3，…等无穷个数字，而图中表现的只是其中一种情况。 当G(1000000) 时也成立吗？
确实，0 以上的整数有无穷个。这就要通过引入"数学归纳法"来证明了。使用数学归纳法能够进行0 以上的所有整数的相关证明。
什么是数学归纳法
数学归纳法是证明有关整数的断言对于0 以上的所有整数（0、1、2、3…）是否成立时所用的方法。
假设现在要用数学归纳法来证明"断言P（n）对于0 以上的所有整数n 都成立"。
数学归纳法要经过以下两个步骤进行证明。这是本章的核心内容，请大家仔细阅读。
o 步骤1 ：
证明"P (0) 成立"。
o 步骤2 ：
证明不论k 为0 以上的哪个整数，"若P (k ) 成立，则P (k +1) 也成立"
在步骤1 中，要证明当k 为0 时断言P(0) 成立。我们将步骤1 称作基底（base）。
在步骤2 中，要证明无论k 为0 以上的哪个整数，"若P( k ) 成立，则P (k+1) 也成立"。
我们将步骤2 称作归纳(induction)。该步骤证明断言若对于0 以上的某个整数成立，则对于下一个整数也成立。
若步骤1 和步骤2 都能得到证明，就证明了"断言P (n) 对于0 以上的所有整数n 都成立"。
以上就是数学归纳法的证明方法。
试着征服无穷数列
数学归纳法通过步骤1（基底）和步骤2（归纳）两个步骤，证明断言P(n) 对于0 以上的所有整数n 都成立。
为什么只通过两个步骤的证明，就能证明无穷的n 呢？请作如下思考。
o 断言P (0) 成立。
理由：步骤1 中已经证明。
o 断言P (1) 成立。
理由：P (0) 已经成立，并且步骤2 中已证明若P (0) 成立，则P (1) 也成立。
o 断言P (2) 成立。
理由：P (1) 已经成立，并且步骤2 中已证明若P (1) 成立，则P (2) 也成立。
o 断言P (3) 成立。
理由：P (2) 已经成立，并且步骤2 中已证明若P (2) 成立，则P (3) 也成立。
这样循环往复，可以说断言P(n) 对于任意数字n 都成立。无论n 为多大的数字都没关系。因为即使设n 为10000000000000000，经过机械式地反复执行步骤2，终究可以证明P（10000000000000000）成立。
这种数学归纳法的思路可以比喻为"推倒多米诺骨牌"。
假设现在有很多多米诺骨牌排成一列。只要保证以下两个步骤，那么无论多米诺骨牌排得有多长最终都能倒下。
o 步骤1
确保让第0 个多米诺骨牌（排头的多米诺骨牌）倒下。
o 步骤2
确保只要推倒第k 个多米诺骨牌，那么第k + 1 个多米诺骨牌也会倒下。推倒多米诺骨牌的两个步骤和数学归纳法的两个步骤一一对应。
数学归纳法并不像"推倒多米诺骨牌"那样关注用时。数学归纳法和编程不同，往往使用的是忽略时间的方法。这就是数学和编程之间最大的差异。
用数学归纳法证明高斯的断言
下面我们就以证明高斯的断言G(n) 为例具体看看数学归纳法。首先讨论断言G(n)。
o 断言G(n) ：0 到n 的整数之和与 相等。
使用数学归纳法就需要通过步骤1（基底）和步骤2（归纳）来证明。
● 步骤1 ：基底的证明
证明G(0) 成立。
G(0) 就是"0 到0 的整数之和与 相等"。
这可以通过直接计算证明。0 到0 的整数之和是0，
至此，步骤1 证明完毕。
● 步骤2 ：归纳的证明
证明当k 为0 以上的任一整数时，"若G(k) 成立，则G(k + 1) 也成立"
现假设G(k) 成立。即假设"0 到k 的整数之和与 相等"。这时，以下等式成立。
假设成立的等式G(k)
下面，我们来证明G(k + 1) 成立。
要证明的等式G(k+1)
G(k + 1) 的左边使用假设的等式G(k) 可以进行如下计算。
而G(k + 1)的右边可以进行如下计算。
G(k + 1) 的左边和右边的计算结果相同。
由此，从G(k) 到G(k + 1) 推导成功，步骤2 得到了证明。
至此，通过数学归纳法的步骤1 和步骤2 都证明了断言G(n)。也就是说通过数学归纳法证明了断言G(n) 对于0 以上的任意整数n 都成立。
求出奇数的和--数学归纳法实例
本节，我们使用数学归纳法来证明另一个断言。
奇数的和
请证明以下断言Q(n) 对于1 以上的所有整数n 都成立。
o 断言Q (n ) ：1 + 3 + 5 + 7 + … +（2 × n -1） = n2
Q(n) 是比较有意思的断言。按从小到大的顺序将n 个奇数相加，得到n2，即平方数n ×n。
这对吗？在证明之前，先通过较小的数n = 1、2、3、4、5 判断Q(n) 的真假。
o 断言Q (1) ：1 = 12
o 断言Q (2) ：1 + 3 = 22
o 断言Q (3) ：1 + 3 + 5 = 32
o 断言Q (4) ：1 + 3 + 5 + 7 = 42
o 断言Q (5) ：1 + 3 + 5 + 7 + 9 = 52
通过以上计算发现断言确实是成立的。
……
展开
