归纳与递归

目录：

数学归纳法介绍

数学归纳法是一种强有力的证明工具。数学归纳法是用来证明定理的工具，但是却不能发现定理。也就是说数学归纳法是一种证明手段。

数学归纳法高中我们也曾学习过，那个时候学习的是不完全归纳法。在离散数学中，我们会学习三种数学归纳法：

• 不完全归纳法（即高中说明的归纳法）
• 强归纳法
• 结构归纳法

这里还会有一些关于递归的知识以及数学归纳法的一些有趣的应用。

本章的参考书籍是《离散数学及其应用》。

不完全归纳法

首先来看看我们都熟悉的不完全归纳法，一般我们就称其为数学归纳法。

关于不完全归纳法，虽然名字有“不完全”三个字，但是这种归纳法恰恰不是不完全的。这种命名只是出于无奈：因为强归纳法也被称为完全归纳法，所以这里的归纳法就被称为不完全归纳法了:blush:。

对于不完全归纳法，大多书上都是以多米诺骨牌来说明的。我们这里使用爬梯子的方式来说明一下：

对于有n节的梯子，我们想要从第一节爬到第n节，可以使用如下的方法：

1. 可以爬到第一节
2. 如果可以爬到第k节，那么我们可以爬到第k+1节

现在我们先假设以上两句都成立，这样可以使用递归的方式来爬到第n节楼梯：首先可以爬到第1节楼梯，然后令k=1，由第二句可知我们可以爬到第2节，再令k=2，则可以爬到第3节。以此类推就可以爬到第n节了。

不完全归纳法定义：

以上两个爬楼梯的步骤其实就是使用数学归纳法描述的。不完全归纳法的定义如下：

为了证明对所有的正整数n，P(n)为真，其中P(n)为一个命题函数，需要完成两个步骤的证明：

基础步骤：证明P(1)为真

归纳步骤：证明对每个整数k来说，蕴含式P(k)→P(K+1)成立。其中P(k)为归纳假设。

这个定义想必大家都很熟悉啦，就是将高中的归纳法定义用离散的语言叙述了一下呗。

对于上面的楼梯问题来说，P(n)就是“能够爬到第n节楼梯”。那么首先证明能够爬到第一节楼梯，即P(1)，然后证明在可以达到P(k)的情况下，可以达到P(k+1)节阶梯。完成以上两个证明就可以达到任意节楼梯啦。

上面的例子是个抽象的生活实例，下面我们给出一些数学上使用不完全归纳法的证明题目：

不完全归纳法实例：

对于求和公式的证明：

不完全归纳的一个用途广泛的地方就是在对求和公式的证明。不过需要注意的是，由于数学归纳法只能用来证明，而不是用来发现定理的，所以想要通过数学归纳法来获得公式是不可能的。只能证明现有公式的正确性。

例1： 证明求和公式1+2+3+...+n=n(n+1)/2是正确的

证明：

　　首先命题函数P(n)是“1+2+3+...+n=n(n+1)/2”，那么首先是基础步骤：

　　　　基础步骤：证明P(1)为真

　　　　　　由于P(1)为1=1*(1+1)/2=1，等式左右两边相等，命题得证。

　　　　归纳步骤：证明在P(k)成立的时候，P(k+1)为真

　　　　　　P(k)为:1+2+3+...+k=k(k+1)/2

　　　　　　P(k+1)为:1+2+3+..+k+1=(k+1)(k+2)/2

　　　这里需要想办法将P(k)变成P(k+1)，很简单，在P(k)左右两边加上k+1即可，那么就是：

　　　　P(k)+k+1=k(k+1)/2+k+1=(k+1)(k+2)/2=P(k+1)

　　　由于P(k)变成P(k+1)之后右式等于P(k+1)的右式。又由于P(k)是真的，所以P(k+1)为真，命题得证。

证明

证明求和公式的题目还有很多，这里先列举一个，其他的题目和这个差不多，只是可能会多一些技巧。

对于不等式的证明：

例2： 证明n<2^n对所有正整数成立

P(n)为"n<2^n对所有正整数成立"

　　基础步骤：P(1)为1<2^1=2成立

　　归纳步骤：P(k)为k<2^k；P(k+1)为 k+1<2^(k+1)

　　　　将P(k)转化为P(k+1)，两边加上1，则

　　　　P(k)+1为k+1<2^k+1

　　　　又由于2^k+1<2(k+1)

　　　　所以k+1<2^k+1<2^(k+1)

　　　即k+1<2^(k+1)成立，P(k+1)成立，命题得证。

证明

对于整除问题的证明：

这种整除问题高中也是难倒了我一段时间啊，这里我们来看看这种题怎么解吧。

例3： 当n为整数时，证明n^3-n可被3整除

基础步骤：P(1)为1^3-1=0可以被3整除
归纳步骤：P(k)为k^3-k,P(k+1)为(k+1)^3-(k+1)
               展开(k+1)^3-(k+1)得k^3+3k^2+3k+1-k-1=（k^3-k)+3*(k^2+k)
可知这个式子能被3整除，证毕。

证明

归纳法的奇特应用：

数学归纳法有时候可以在一些意想不到的场合使用，来看看下面的问题：

例4： 使用右三联骨牌可以覆盖一个2^n × 2^n棋盘并且让棋盘只留下一个空格

这个就是右三联骨牌，进行旋转的话还可以得到另外三种：

那么首先来证明P(1)的情况

基础步骤：当k=1的时候，棋盘为2 × 2的，那么只需要上面任何一个骨牌就可以覆盖，命题的证。

归纳步骤：在2^k × 2^k的棋盘下满足条件，那么2^(k+1) × 2^(k+1)也可以满足条件

我们将整个棋盘分为四份：

由P(k)知，右下角的子棋盘一定可以使用骨牌的只剩下一个空格：

接下来我们这样放上一个骨牌：

这样的话剩下的三个棋盘中多出的空格就被填满了，这样由P(k)知可以全部填满。所以最后整个棋盘只会剩下有下家一块空格，命题得证。

强归纳法（完全归纳法）

有些时候使用不完全归纳法不容易证明一些命题，这个时候我们可以考虑强归纳法来证明。

强归纳法的定义：

要证明对于所有的正整数n而言，都有P(n)为真，其中P(n)为命题函数，我们需要证明以下两个步骤：

基础步骤：

P(1)成立

归纳步骤：

对于所有的正整数 n来说，蕴含式[P(1)∧P(2)∧P(3)∧...∧P(k)]→P(k+1)成立。其中P(1)∧P(2)∧P(3)∧...∧P(k)为归纳假设。

注意到强归纳法和不完全归纳法只在归纳步骤上有区别。不完全归纳法是从P(k)推导到P(k+1)。而强归纳法则是从前P(k)个条件推导到P(k+1)个条件。

有些时候强归纳法毕不完全归纳法更好用。所以我们使用归纳法的顺序是先想到强归纳法，再想到不完全归纳法。

强归纳法的一些实例：

例1： 证明若n是大于1的整数，则n可以写成素数之积

基本步骤：

　　对于2来说，显然其本身就是素数

归纳步骤：

　　如果k+1是素数，那么显然其本身就是素数，命题成立。

　　如果k+1是合数，那么一定存在i，j满足2<=i<=j<k+1且k+1=i*j。因为i，j都小于等于k，所以由P(k)的正确性知道i，j都可以写成素数之积。那么k+1可以写成素数之积，那么P(k+1)成立

证明

也可以使用强归纳法来证明一些生活中的问题

例2： 考虑一个取火柴的游戏，其中两名选手轮流从两堆火柴中的一对取出任意数目整数的火柴，取走最后一根火柴的人获胜。求证：当每堆开始有n根火柴的时候，后手一定会赢。

这个题目的意思就是说，有两堆数量一样的火柴，有两名选手从其中取火柴，但是一次只能在一个火柴堆中取。最后将所有火柴都取走的人获胜。要求证明第二步走的人一定会获胜。

基础步骤：

　　当n=1的时候，先手只有一种选择：从两个火柴堆里面选一个拿完（因为每个火柴堆只有一根火柴）。这个时候后手就可以将另外一根火柴拿走了。命题得证。

归纳步骤：

　　首先归纳假设是当一堆火柴有i个火柴（1<=i<=k）的时候命题得证。现在需要证明每堆有k+1根火柴的时候命题的证。这个时候假如先手拿了r根火柴，后手可以在另外一堆例同样拿r根火柴。这样两堆的火柴数就是k+1-r(1<=k+1-r<=k)，这个时候条件就变成了归纳假设的条件。由归纳假设可知命题为真。

证明

递归定义和结构归纳法

所谓递归定义，相信每个学计算机的都知道，就是在定义自己的时候在自己的定义里面再次使用自己的定义。

递归定义函数：

基础步骤：规定这个函数在0处的值

递归步骤：给出从较小值求出当前值的规则

在数学里面其实就是复合函数啦。最最有名的递归定义函数就是裴波那契数列啦：

裴波那契数f0,f1,f2...是用方程组f0=0,f1=1,fn=fn-1+fn-2来递归定义的函数。

递归定义结构和集合：

像是递归定义函数一样，递归定义集合和结构也是有基础步骤和递归步骤的。看看下面三个递归定义：

定义1：

考虑如下定义的整数集合的子集S：

基础步骤：3∈S

递归步骤：若x∈S且y∈S，那么x+y∈S

这个递归定义定义了一个数集，其中包括3，6，9，12等等数。

定义2：

字母表A上的字符串集合A'递归的定义成：

基础步骤：空串λ∈A'

递归步骤：如果ω∈A'且x∈A，那么ωx∈A。这里ωx为字符串的连接，指将x串连接在ω串后面。

这里递归的定义了字符串。

在数据结构中有很多递归的定义，包括链表的结构体定义，二叉树的结构体定义和图的邻接表定义。可以看出递归定义在计算机中还是有重要的地位的。

结构归纳法的定义：

结构归纳法是专门用于证明递归结构定义的一种归纳法：

基础步骤：证明对于递归定义的基础步骤所规定的属于该集合的所有元素来说，结果成立

归纳步骤：证明如果对于定义的递归步骤中用来构造新元素的每个元素来说命题为真，那么对于这些新元素来说结果成立。

结构归纳法的例子：

这里举个例子来说明结构归纳法如何证明：

首先来看一下关于满二叉树的一些递归定义：

满二叉树：

基础步骤：存在一个只有单个定点的满二叉树

归纳步骤：如果T1，T2都是满二叉树，则存在一个表示为T1 • T2的满二叉树，它包含树根r和连接从r到左子树T1和右子树T2的边

满二叉树高度h(T )：

基础步骤：只含有树根r的满二叉树T的高度是h(T)=0

归纳步骤：如果T1，T2都是满二叉树，则满二叉树T=T1 • T2有高度h(T)=1+max(h(T1),h(T2))

定义满二叉树节点数目n(T)：

基础步骤：只含有树根r的满二叉树T的高度h(T)=0

递归步骤：如果T1，T2都是满二叉树，则满二叉树T1 • T2的节点数是n(T)=1+n(T1)+n(T2)

例1：

如果T为满二叉树，那么证明n(T)<=2^[h(T)+1]-1

基础步骤：当T只有树根时，n(T)=1<=2^(0+1)-1=1成立

归纳步骤：对于归纳假设，当T1和T2都是满二叉树的时候，n(T1)<=2^[h(T1)+1]-1且n(T2)<=2^[h(T2)+1]-1成立。根据n(T)和h(T)的递归公式知道n(T)=1+n(T1)+n(T2)，h(T)=1+max(h(T1),h(T2))。带入公式知道：

n(T)=1+n(T1)+n(T2)

　　<=1+(2^[h(T1)+1]-1)+(2^[h(T2)+1]-1)

　　<=2*max(2^[h(T1)+1]-1,2^[h(T2)+1]-1) -1

　　<=2*2^max(2^[h(T1)+1]-1,2^[h(T2)+1]-1) -1

　　=2^[h(T)+1] -1

命题成立

证明