牛津大学数学院在其官网同步存放着各种数学课程的课件，详情参考其官网链接. 本文以及可能会有的今后的一个系列，就是对上述内容阅读学习所做的笔记。
牛津数学导论 （2019-2020）学习笔记【1.2】归纳法
数学的陈述有时候可简单了,就一句话,比如: $$ \begin{aligned} 3&< \pi \ 0&<x<y \implies x^2<y^2 \end{aligned} $$
不过有时候可能也很复杂,比如: $$ \begin{aligned} \text{A}& 2^{x} >0, \text{x为任意实数}\ \text{B}&\text{平面中的n条线,任意两条都不平行,任意三条都不共节点,会将该平面分成}n(n+1)/2+1\text{个区域,}n=1,2,3,..\ \text{C}&\int_0^{\pi} sin^{2n} \theta d \theta = \frac{(2n)!\pi}{(n!)^22^{2\pi}}\text{其中}n=0,1,2,3,... \ \text{D}& \text{对所有的}n=2,3,4,...,\text{都可以将}2n\text{写成两个质数(prime)的和.}\ \end{aligned} $$
归纳法(induction),或者更严格说叫数学归纳法(mathematical induction)是用来在这种很多复杂声明情景下进行证明的一种行之有效的方法,比如上面那些至少有三段生命以上的,都通过自然数进行索引的(indexed),或者是整数,又或者是整数的某种子集的情况.本课程例题7就是对上面的声明B使用归纳法进行的证明.声明B和C都可以使用归纳法来证明,因为这两个例子有一个共同点,就是一旦知道第n个声明为真,就可以证明下一个即第(n+1)个声明也是真的.这其实就是归纳法背后的核心思想.上面的声明D就是一个很著名的开放问题了,也就是哥德巴赫猜想(Goldbach’s Conjecture).如果设$D(n)$为要判断的对象,也就是要证明 2n 可以写成两个素数的和,目前所知的是一直到$n\le 4\times 10^{18}$范围内都是成立的.这个命题怎么就和B与C不同,而且很棘手不能归纳呢?原因就在于在这个问题中，即便是我们已经知道了$D(n)$的信息,也并不能有助于我们去确定$D(n+1)$,所以就不能以这样的方式来构建归纳证明.例如,我们可以确定$D(19)$和$D(20)$,即:
在给出归纳法的正规定义之前,先举个例子来利用归纳法证明一下命题B.
平面上的 n 条线,任意两者不平行,任意三者不共点,则可以分割出$n(n+1)/2+1\text{个区域,}n=1,2,3,..$
证明$B(0)$:当一个平面没有线的时候,很明显就只有一个区域,所以放到上面的推导公式中就是当$n=0$的时候得到的结果是1.
考虑$B(n)$然后证明$B(n+1)$,假如已经有了$n$条线,已经切出来了$n(n+1)/2+1$个分出来的区域,新加进来的第$n+1$个线条加进来之后就要跟之前的全部$n$条线相交.因为题设条件就是这条线不能和之前的任何一个线平行的.另外新加入的线还要和之前的每一根线都有一个单独的交叉点,因为题设说了是任意三条线不共点.这样的$n$个交叉点就会将这条新线切割成了$n+1$段.
对这$n+1$段线段来说,每一个都对应两个区域,两侧各一个,而之前该线段所在位置本来只有一个区域.所以通过增加这第$n+1$根线,就是创造了$n+1$个新的区域.所以这样就有对应$n+1$的区域数$B(n+1)$:
这样得到的表达式就符合题设中所给公式在$(n+1)$时候的形式.这个证明过程就是归纳,证明完毕.
已经被证明为真的第一条语句(比如上面例子里面的$B(0)$)就叫初始条件(initial case)或者初始步骤(initial step), 设第
一定要确定理解了样例7:这个例子里面包含了归纳法证明的最常规的各个重要步骤.
- 要特别注意到在上面的例7的证明步骤中,最后一步又带回了原始的公式形式$n(n+1)/2+1$, 区别只是在公式中用$n+1$替代了$n$;这就是我们之前所说的能够向前推进的表达式,也就是所谓的"递推公式".
通过归纳,我们现在就知道了B为真.也就是说对于任何的$n\ge1$,$B(n)$都是真.咋就知道了呢?咱们就先试着证明$B(3)$为真,那就需要正明显的几个命题:
这就能知道$B(3)$为真了.然后就这样建立逻辑链,就可以最终证明任何的$B(n)$都是真的.
归纳法原理正式写来如下所示:
设$P(n)$是一个命题族,索引为自然数$n=0,1,2,...$. 假设有:
- 初始步骤(initial step)
$P(0)$ 为真; - 归纳步骤(inductive step) 对任意$n\ge N$,若$P(n)$为真,则$P(n+1)$为真. 由此可知$P(n)$对于所有的$n\ge 0$都为真.
设$S$是使得$P(n)$为真的自然数所组成的集合.由于$P(0)$为真,可知$0\in S$.接下来,若有$n\in S$使得$P(n)$为真,则$P(n+1)$为真,或者等价的是$n+1\in S$. 这样集合$S$就有下面的性质:(i)$0\in S$,(ii)如果$n\in S$,则$n+1\in S$.由于自然数集合$N$是满足这些性质的最小子集,所以自然数集合$N$应该被集合$S$所包含.因此有$S=N$,证明完毕.
设$N$是 一个整数(integer),然后设$P(n)$是针对$n\ge 0$的一系列命题族.设有:
- 初始步骤(initial step)
$P(0)$ 为真; - 归纳步骤(inductive step) 对任意$n\ge 0$, 如果$P(1),P(2),P(3),...P(n)$都为真能推出$P(n+1)$为真. 则$P(n)$对于所有的$n\ge 0$都为真.
对$n\ge 0$,设$Q(n)$是命题:$P(k)$对于所有$0\le k \le n$的$k$都成立. 上面定理的假设就可以等价表达为:(i)$Q(0)$(就相当于上面定理表述中的$P(0)$相当)为真;(ii)如果$Q(n)$为真,则$Q(n+1)$也为真.然后按照定理9所述过程进行归纳,就知道对于所有的$n$都有$Q(n)$为真.由于$P(n)$是$Q(n)$的一个结果(consequence),所以可知$P(n)$也是对所有的$n$来说都为真.证明完毕.
作为归纳法的一个结果(consequence),现在就可以得到:
设一个反命题,用矛盾法/反证法来证明.假设有一个集合$S$是自然数集合$N$的子集,但没有最小元素,然后定义
然后就能发现$S^*=N$,也就是结论就是$S$是空集,这就形成了矛盾.
要注意$0$是属于$S^$的.若非如此,则$0$就在$S$中了,这样$S$就有一个最小元素,即$0$.现在假设$n$在$S^$中.这就意味着$0,1,2,3,...,n$中的任意一个都不属于集合$S$.接着推导就是$n+1$也不属于$S$,否则就这一项就是集合$S$中的最小元素了.因此$0,1,2,3,...,n,n+1$中没有元素属于$S$或者等价地说$n+1$也属于集合$S^$. 通过归纳可知$S^=N$,所以集合$S$只能是空集.证明完毕.
一个由自然数组成的严格递减序列(strictly decreasing sequence)是有界的(finite).
设自然数的一个子集为${x_1,x_2,x_3,...,x_n}$.假设其中最小元素就是这个$x_n$.如果$x_n$不是列表中的最后一个元素,就有了$x_n>x_{n+1}$,这就和$x_n$是最小元素相冲突.因此可知这个递减序列是有界的,最终就终止在最小的$x_n$处.证明完毕.
#####注：
推论10就是通常所说的第二数学归纳法, 或者叫强数学归纳法. 上面给出的证明, 其实是用数学归纳法 (第一数学归纳法) 来证明第二数学归纳法. 在这里, 命题$Q(n)$事实上起到了一个“转换”的作用, 把“对$1,2,...,n$都成立”转换“成对$n$成立, 接着再用第一数学归纳法就可以证明第二数学归纳法了. 这个事实表明, 不严格地说, 第二数学归纳法更像是第一数学归纳法的一个类似”语法糖“的东西.
关于第二数学归纳法, 它其实还可以变成下述形式: 对于包含$1$的正整数集合, 如果它具有下面的性质: 对每一个正整数$n$, 如果它包含$1,2,...,n$, 则它也包含$n+1$, 那么就说明这个集合一定包含了所有的正整数.
对于第二数学归纳法的应用, 下面用一个例子来说明一下 .
证明：任何多于$1$分钱邮资, 都可以用$2$分钱和$3$分钱的邮票来构成. 基础步骤就是:
注意这个证明里, 因为需要用到$n-1$, 所以最开始的步骤必须有两部分组成, 也就是对$2$和$3$都成立, 否则这个$n-1$你就用不了. 而也是因为这个因素, 所以用第二数学归纳法证明起来就很自然, 用第一数学归纳法就需要多说很多话.
如果一个递推不仅仅是关于$n$和$n-1$的关系的, 而是关于$n$和$n-1,n-2$甚至更往前的自然数的关系, 那么用第二数学归纳法就更加方便一些.