数学归纳法

这是数学思维系列的第一篇,希望可以养成写写博客、看看视频、做做练习、探索数学的好习惯。

数学归纳法与归纳法的差异

数学归纳法与归纳法有什么差异呢?归纳法是我们用来观察有限个例子所共有的性质时常使用的推理方法,由比较归纳的程序,我们便能提出假设。
然而,这个假设的有效性,只能适用于这些我们所观察的有限例子上。如何证明这个假设的有效性可以推广到一般的情形呢?这时,就必须借助数学归纳法來帮忙。

数学归纳法的数学基础

数学归纳法的数学基础是什么?它的数学基础奠定在意大利数学家皮亚诺 (Peano, 1858-1932) 于 1889 年所提出的「皮亚诺公理」(Peano′saxioms) 之上。皮亚诺从不加定义的『集合』、『自然数』、『后继元素』和『属于』等概念出发,给出了关于自然数的五条公理:

  1. 1 是一个自然数。
  2. 1 不是任何其他自然数的后继元素。
  3. 每一个自然數 a 都有一个后继元素。
  4. 如果 a 与 b 的后继元素相等,则 a=b。
  5. 若一个由自然数所组成的集合 S 包含 1,并且当 S 包含某一自然數 a 时,它一定也含有 a 的后继元素,则 S 就包含有全体自然数。

其中的公理 (5) 就是所谓的『数学归纳法原理』(the Principle of Mathematical Induction)。

数学归纳法证明陈述的形式,以及为什么它是靠谱的

使用数学归纳法证明陈述的过程分为两步:

  1. 证明基础情况是成立的
  2. 进行归纳

有一个陈述P(n),我们认为它是正确的,使用数学归纳法证明它的形式如下:

  1. 当 n=1 时,P(1) 成立 (归纳起点,the basis of Induction)
  2. 假设 n=k 时 P(k)成立; (归纳假设,Induction hypothesis)
    证明 n=k+1 时 P(k+1)也成立。 (归纳步骤,Induction step)

首先我们核实了「n=1 时 P(1) 成立」;接着我们又证明了「假设 n=k 时 P(k)成立,那么 n=k+1 时 P(k+1)也成立」。
现在将 n=1 应用于第二步得出的结论,就会发现因为 P(1) 成立,所以 P(2) 也成立;因为 P(2) 成立,所以 P(3) 也成立,如果循环递推下去,那么 P(n) 对所有自然数都成立,所以它是正确的。

光说不练是假把式

证明前 n 个自然数之和 $S(n) = \frac{n(n+1)}{2}$

  1. 当 n=1 时,$S(1) = \frac{1*(1+1)}{2} = 1$,成立
  2. 假设 n=k 时 $S(k) = \frac{k*(k+1)}{2}$ 成立;
    当 n=k+1 时 $S(k+1) = 1+2+3+...+k+(k+1) = S(k)+(k+1) = \frac{k*(k+1)}{2} + \frac{2*(k+1)}{2} = \frac{(k+1)(k+1+1)}{2}$
    到此已经证明了 n=k+1 时 S(k+1)也成立。
    因此 $S(n) = \frac{n(n+1)}{2}$ 对所有自然数 n 均成立。

证明一个不那么数学的陈述

有这么一道傻逼面试题:一个屋子里面有50个人,每个人领着一条狗,而这些狗中有一部分是病狗。

假定有如下条件:

  1. 狗的病不会传染,也不会不治而愈
  2. 狗的主人不能直接看出自己的狗是否有病,只能靠看别人的狗和推理,来发现自己的狗是否有病
  3. 一旦主人发现自己的狗是病狗,就会在当天开枪打死这条狗
  4. 狗只能由他的主人开枪打死

如果他们在一起,第一天没有枪声,第二天没有枪声……第十天发出了一片枪声,问有几条狗被打死了?(不是脑筋急转弯!)

刚听完这道傻逼面试题时,脑子有点懵,感觉好像有点无从下手。不一会儿,就开始尝试从最简单的情况入手。不过,有一个易忽略的隐式条件,这些狗中有一部分是病狗,不存在没有病狗的情况:

  1. 假设只有一条病狗,那狗主人第一天观察其他狗都正常,而题目中又说一定有病狗,就能确定自己的是病狗,必定会在第一天开枪打死它
  2. 假设有两条病狗,第一天这两个主人通过观察其他狗,都发现了一条病狗,但对自己的狗是否有病并未形成判断,所以第一天没有枪声;第二天醒来发现第一天没有枪声,基于 假设 1,他俩就知道肯定不止一条狗有病,但是自己只看到了一条病狗,那另一条肯定是自己的,所以第二天会有两声枪响
  3. 假设有三条病狗,第一天这三个主人都发现了两条病狗,但前两天都没有枪声,就知道病狗肯定不止两条,然后就… 你懂滴!
    依次类推下去,那第 10 天就会有 10 声枪响。

我们使用数学归纳法来证明这个结论的有效性。要证明的陈述:若第 n 天有枪声,那就有 n 条病狗。

  1. n=1 时,即第一天就有枪声。用反证法,假设有 m(m>1) 条病狗,第一天主人们只能发现 m-1 条病狗,并且也不确定实际总共有多少条病狗,因此不会有枪声,进而假设不成立。因此 n=1 时陈述成立。
  2. 假设「 n=k 时陈述成立」;那么 n=k+1 即第 k+1 天才有枪声时,已知前 k 天都没有枪声,由此可推知第 k 天主人们只是发现了 k 条病狗,并不能确定自己的狗是否是有病,所以才没有枪声,到了第 k+1 天,他们就能确定不止有 k 条病狗,既然只看到了 k 条,那自己的肯定是病狗,所以就会有 k+1 声枪响。到此「 n=k+1 时陈述也成立」。

这就完成了该陈述的证明。不过这道题傻逼的地方有两点:

  1. 题目并未说明主人就一定能看出其他狗中的病狗,以及花多久才看得出来。一旦纠结在这些点上面试就悲剧了
  2. 整个命题描述的情形现实中不可能发生,纯属为了考人而出的蛮横不讲理的傻逼题目

参考资源

  1. 台湾关于数学归纳法教授的思考
0%