《程序员的数学（第2版）》中的数学归纳法魅力

图灵在陆续出版计算机图书的同时，便早早意识到数学对于程序员进阶和提升的重要性，因此这套《程序员的数学》便应运而生，到今天已经出版了4本，成为众多程序员手中必不可少的数学学习书。

整套书配上有趣易懂的图解教程，没有晦涩的公式，只有好玩的数学题，阐述编程需要的基础数学知识和数学思维，成为众多人的不二之选。累计已畅销26万册。

我们选取其中的一个章节：数学归纳法，一起来感受这本书的魅力吧！

来源 | 《程序员的数学（第2版）》

作者 | [日]结城浩

译者：管杰 卢晓南

数学归纳法是证明某断言对于 0 以上的所有整数（0, 1, 2, 3, ···）都成立的方法。0 以上的整数 0, 1, 2, 3, ··· 有无穷个，但若使用数学归纳法，只需要经过“两个步骤”，就能证明有关无穷的命题。

首先，我们以求出 1 到 100 之和为例介绍数学归纳法。接着会穿插几道思考题来看一下数学归纳法的具体实例。最后，我们会讨论数学归纳法和编程的关系，一起了解一下循环不变式。

1高斯求和

思考题（存钱罐里的钱）

在你面前有一个空存钱罐。

• 第 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 即可，结果为 10 100。不过 10 100 是要求的数的 2 倍，因此还得除以 2，答案为 5050。

答案：5050 元。

讨论一下小高斯的解答

小高斯的方法可谓绝妙非凡！

为了便于大家理解，我们将小高斯的方法用图来表示。求 1 + 2 + 3 + ··· + 100 的结果，相当于计算图 4-1 所示的排列成阶梯型的瓷砖块数。

图 4-1　将小高斯的方法图形化

小高斯则又做了一个一模一样的阶梯，并将两者合二为一，组成了一个长方形（图 4-2）。

图 4-2　将两个阶梯组合成一个长方形

由两个阶梯组合而成的长方形，纵向有 101 块瓷砖，横向有 100 块瓷砖。因此，该长方形由 101 × 100 = 10 100 块瓷砖构成。而所求的瓷砖块数就是 10 100 的一半，即 5050。

我们来说一说小高斯的计算效率。使用他的方法不需要花费力气逐个相加。只要将两端的 1 和 100 相加，结果乘以 100 再除以 2 就行了。

现在，假设我们不是从 1 加到 100，而是从 1 加到 10 000 000 000（100 亿）。这次我们就不能采用逐一相加的方法了。因为即使计算器 1 秒能完成 1 次加法计算，加到 100 亿也得花 300 年以上的时间。

不过，如果使用小高斯的方法，那么从 1 加到 100 亿也只要 1 次加法、1 次乘法、1 次除法运算即可完事。我们来实际计算一下。

高斯（Karl Friedrich Gauss，1777——1855）后来成为了历史上著名的数学家。

归纳

小高斯运用了以下等式。

这里，使用变量 ，将“1 到 100”归纳为“0 到 ”。这样，上面的等式就变为如下形式。

那么，这个等式对于 0 以上的任意整数  都成立吗？即  为 100、200，或者 100 万、100 亿时该等式也都成立吗？如果成立的话，又如何来证明呢？

这种时候就要用到数学归纳法了。数学归纳法是证明“断言对于 0 以上的所有整数  都成立”的方法。

2数学归纳法—如何征服无穷数列

本节，我们就来讨论一下数学归纳法的相关内容。首先，从“0 以上的整数的断言”开始学起，然后使用数学归纳法来证明小高斯的断言。

0 以上的整数的断言

“0 以上的整数  的断言”，就是能够判定 0, 1,2 等各个整数为“真”或“假”的断言。这样说明或许难以理解，下面就举几个例子。

• 例 1

  ，即“ 为偶数”的断言。由于  为 0 时， 为偶数，所以  为真。

   又怎么样呢？因为  为偶数，所以  也为真。

  那是否可以说断言 ，对于 0 以上的所有整数  都为真呢？

  对！可以这么说。因为 0 以上的任意整数乘以 2 的结果都为偶数，所以对于 0 以上的所有整数，断言  都为真。

• • 断言 ： 为偶数

• 例 2

  那么，断言  又将如何呢？该断言对于 0 以上的所有整数  都成立吗？

  例如，假设  为 1，则断言  就是“1 × 3 为奇数”，这个结果为真。但不能说对于 0 以上的所有整数 n，断言  都为真。因为假设  为 2，则  的值为 2 × 3 = 6。而 6 是偶数，所以断言  不为真（为假）。

   是推翻“断言  对于 0 以上的所有整数  都成立”的反例之一。

• • 断言 ： 为奇数

• 其他例子

  那么请思考一下，在下面 4 个断言中，对于 0 以上的所有整数  都成立的有哪些。

  断言 ，对于 0 以上的所有整数  都成立。因为若  为 0 以上的整数，则  肯定是 0 以上的整数。

  断言 ，对于 0 以上的所有整数  不成立。例如，断言  为假。因为 0 – 1 = -1，不是 0 以上的整数。 是唯一的反例。

  断言 ，对于 0 以上的所有整数  都成立。

  断言 ，对于 0 以上的所有整数  不成立。因为当  为奇数时， 的结果不是整数。

• • 断言 ： 为 0 以上的整数
  • 断言 ： 为 0 以上的整数
  • 断言 ： 为 0 以上的整数
  • 断言 ： 为 0 以上的整数

小高斯的断言

在讨论了“0 以上的整数  的断言”之后，我们将话题转回小高斯的断言。

可以使用下述有关  的断言形式来表现小高斯的观点。

• 断言 ：0 到  的整数之和为 

接下来要证明的是，“ 对于 0 以上的所有整数  都成立”。可以通过描画前面的阶梯状的图（图 4-1）来证明，但是有人可能会有这样的疑问：0 以上的整数有 0, 1, 2,3 等无穷个数，而图中表现的只是其中一种情况。当  时也成立吗？

确实，0 以上的整数有无穷个。这就要通过引入“数学归纳法”来证明了。使用数学归纳法能够进行 0 以上的所有整数的相关证明。

3什么是数学归纳法

数学归纳法是证明有关整数的断言对于 0 以上的所有整数（0, 1, 2, 3, ···）是否成立时所用的方法。

假设现在要用数学归纳法来证明“断言  对于 0 以上的所有整数  都成立”。

数学归纳法要经过以下两个步骤进行证明。这是本章的核心内容，请大家仔细阅读。

• 步骤 1

  证明“ 成立”

• 步骤 2

  证明不论  为 0 以上的哪个整数，“若  成立，则  也成立”

在步骤 1 中，要证明当  为 0 时断言  成立。我们将步骤 1 称作基底（base）。

在步骤 2 中，要证明无论  为 0 以上的哪个整数，“若  成立，则  也成立”。我们将步骤 2 称作归纳（induction）。该步骤证明断言若对于 0 以上的某个整数成立，则对于下一个整数也成立。

若步骤 1 和步骤 2 都能得到证明，就证明了“断言  对于 0 以上的所有整数  都成立”。

以上就是数学归纳法的证明方法。

试着征服无穷数列

数学归纳法通过步骤 1（基底）和步骤 2（归纳）两个步骤，证明断言  对于 0 以上的所有整数  都成立。

为什么只通过两个步骤的证明，就能证明无穷的  呢？请作如下思考。

• 断言  成立

  理由：步骤 1 中已经证明。

• 断言  成立

  理由： 已经成立，并且步骤 2 中已证明若  成立，则  也成立。

• 断言  成立

  理由： 已经成立，并且步骤 2 中已证明若  成立，则  也成立。

• 断言  成立

  理由： 已经成立，并且步骤 2 中已证明若  成立，则  也成立。

这样循环往复，可以说断言  对于任意整数  都成立。无论  为多大的整数都没关系。因为即使设  为 10 000 000 000 000 000，经过机械式地反复执行步骤 2，终究可以证明  成立。

这种数学归纳法的思路可以比喻为“推倒多米诺骨牌”。

假设现在有很多多米诺骨牌排成一列。只要保证以下两个步骤，那么无论多米诺骨牌排得有多长最终都能倒下。

• 步骤 1

  确保让第 0 个多米诺骨牌（排头的多米诺骨牌）倒下

• 步骤 2

  确保只要推倒第  个多米诺骨牌，那么第  个多米诺骨牌也会倒下

推倒多米诺骨牌的两个步骤和数学归纳法的两个步骤一一对应。

数学归纳法并不像“推倒多米诺骨牌”那样关注所用的时间。数学归纳法和编程不同，往往使用的是忽略时间的方法。这就是数学和编程之间最大的差异。

用数学归纳法证明小高斯的断言

下面我们就以证明小高斯的断言  为例具体看看数学归纳法。首先讨论断言 。

• 断言 ：0 到  的整数之和与  相等

使用数学归纳法就需要通过步骤 1（基底）和步骤 2（归纳）来证明。

• 步骤 1：基底的证明

  证明  成立。

   就是“0 到 0 的整数之和与  相等”。

  这可以通过直接计算证明。0 到 0 的整数之和是 0， 也是 0。

  至此，步骤 1 证明完毕。

• 步骤 2：归纳的证明

  证明当  为 0 以上的任一整数时，“若  成立，则  也成立”。

  现假设  成立。即假设“0 到  的整数之和与  相等”。这时，以下等式成立。

  假设成立的等式 

  

  下面，我们来证明  成立。

  要证明的等式 

  

   的左边使用假设的等式  可以进行如下计算。

  

  而  的右边可以进行如下计算。

  

   的左边和右边的计算结果相同。

  由此，从  到  推导成功，步骤 2 得到了证明。

  至此，通过数学归纳法的步骤 1 和步骤 2 证明了断言 。也就是说通过数学归纳法证明了断言  对于 0 以上的任意整数  都成立。

求出奇数的和—数学归纳法实例

本节，我们使用数学归纳法来证明另一个断言。

通过数学归纳法证明

请证明以下断言  对于 1 以上的所有整数  都成立。

• 断言 ：

 是比较有意思的断言。按从小到大的顺序将  个奇数相加，得到 ，即平方数 。这对吗？在证明之前，先通过较小的数  判断  的真假。

• 断言 ：
• 断言 ：
• 断言 ：
• 断言 ：
• 断言 ：

通过以上计算发现断言确实是成立的。

通过数学归纳法证明

下面我们来证明“断言  对于 1 以上的所有整数  都成立”。为此，需要通过数学归纳法的两个步骤进行证明。

虽然这次要证明的不是“0 以上的……”，而是“1 以上的……”，但只要将 0 换成 1 来进行基底的证明就可以使用数学归纳法了。

• 步骤 1：基底的证明

  证明  成立。

  因为 ，所以确实成立。

  步骤 1 证明完毕。

• 步骤 2：归纳的证明

  证明  为 1 以上的任意整数时，“若  成立，则  也成立”。现假设  成立，即以下等式成立。

  假设成立的等式 

  

  下面证明  等式成立。

  要证明的等式 

  

   的左边使用假设的等式  可以进行如下计算。

  

  而  的右边可以进行如下计算。

  

   的左边和右边计算结果相同。

  由此，从  到  推导成功，步骤 2 得到了证明。

  至此，通过数学归纳法的步骤 1 和步骤 2 证明了断言 Q(n)。也就是说，通过数学归纳法，证明了断言  对于 1 以上的任意整数  都成立。

图形化说明

断言  也可以用图来进行说明。下面我们来看看  的图示（图 4-3）。

图 4-3　 的图示

1 块瓷砖、3 块瓷砖、5 块瓷砖、7 块瓷砖、9 块瓷砖可以构成 5 × 5 的正方形。这正好相当于断言 。

推荐阅读

《程序员的数学》（系列全四册）

机器学习、数据挖掘、模式识别基础知识，热销书程序员的数学系列套装，IT计算机编程基础数据教程书籍，掌握编程所需的基础数学知识和数学思维。