图灵在陆续出版计算机图书的同时,便早早意识到数学对于程序员进阶和提升的重要性,因此这套《程序员的数学》便应运而生,到今天已经出版了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计算机编程基础数据教程书籍,掌握编程所需的基础数学知识和数学思维。