数学归纳法及例题分析

前言

学算法，不得不提的就是数学归纳法。许多算法都会用到归纳假设的思想，其追溯回去便是数学归纳法。

数学归纳法

最简单和常见的数学归纳法是证明当n等于任意一个自然数时某命题成立。证明分下面两步：

1. 证明当n = 1时命题成立。
2. 证明如果在n = k时命题成立，那么可以推导出在n = k+1时命题也成立。（k代表任意自然数）

这种方法的原理在于：首先证明在某个起点值时命题成立，然后证明从一个值到下一个值的过程有效。当这两点都已经证明，那么任意值都可以通过反复使用这个方法推导出来。把这个方法想成多米诺效应也许更容易理解一些。例如：你有一列很长的直立着的多米诺骨牌，如果你可以：

1. 证明第一张骨牌会倒。
2. 证明只要任意一张骨牌倒了，那么其下一张骨牌也会因为前面的骨牌倒而跟着倒。

那么便可以下结论：所有的骨牌都会倒下。

应用举例

1. 前n项和

证明：S(n) = 1 + 2 + 3  ….  + n 前n项和为n(n + 1) / 2

n = 1, S(1)  = 1

假设n时命题成立

N+ 1时，

S（n  + 1） 

=  S(n) + n + 1

= n(n + 1)/2 + n + 1

= (n + 1)(n + 2)/ 2

成立

2. 区域计数

问n条居一般位置的直线能将平面分成多少个区域

定义：一般位置， 任意两线不平行，任意三线不共点。

现在草稿纸上看看简单的情况，看看有没有规律。

直线 — 区域

1 —  2

2 — 4

3 — 7

4 — 11

 

 

找规律 第n条直线能比n-1条直线的区域多n个

证明： 在平面内n- 1条居一般位置的直线添加一条直线会增加n个区域

n <= 3 时 显然成立

假设n-1条直线时成立

加入第n条直线

假设删去第n – 1条直线，

根据假设，这样加入的第n条增加了n – 1区域

而放回第n-1条直线，直线l(n)与l（n-1）必然在某一个区域R里面相交

本来对于一个区域，l（n）穿过可以多出来一个区域

因为l（n – 1）的存在，在R中l（n）多分出两块，其他还是一样

所以l（n）多分出n块区域

成立

3. 着色问题

证明：平面上任意直线构成的区域可以用两种颜色进行着色，相邻的区域颜色不同

n = 1, 显然成立

假设n – 1条直线情况下成立

对于n条直线

加入第n条直线ln

ln 左边的区域所有颜色不变

ln 右边的区域所有颜色翻转

两种情况

1. 两区域在同一边，原来不同，加入ln，要么都不变，要么都翻转，还是不同
2. 两区域的原来是一块的，颜色相同，被ln分开，一边翻转了，颜色不同

命题成立

4. 金字塔求和

证明：第i行的和为i^3

要证第i行的和为i^3

即证第i+1行和-第i行和 =（ i+1)^3 – （i）^3

而看图

i行有i个数

i行第一个与i+1行第一个相差2*i

两两相减，最后多一个

2 * i* i + x= （ i+1）^3 – （i）^3

即证明i行最后一个数为[（ i+1）^3 – （i）^3] –  2 * i * i = i^2 + 3 * i +1

即证明i+1行最后一个 – i行最后一个是（i+1）^2 + 3 * (I+1) +1 –  [ i2 + 3 * i +1] = 2i + 2

由于前面已经看到i+1行与i行前面两两对其相差2I, 所以最后一个相差2i + 2

命题成立

5. 简单不等式

证明1/2+1/4+1/8+…+1/2^n<1. n = 1, 1/2 < 1, 成立 假设1/2+1/4+1/8+…+1/2^n <1 成立 n+1时 按常规一般证明 1/2+1/4+1/8+…+1/2^n+1/2^(n+1) 前面<1, 加个1/2^(n+1)很难说还<1 没法证 换个思路 1/2+1/4+1/8+…+1/2^n +1/2^(n+1) = 1/2+（1/4+1/8+…+1/2^n +1/2^(n+1) ） = 1/2+1/2 (1/2+1/4+1/8+…+1/2^n ) < 1/2+1/2=1 成立 原命题得证 

6. 欧拉公式

图论

面，图中边所围的封闭区域，整个外面也算一个面

证明：任意一连通图，节点数V, 边数E, 面数F， 满足 V + F = E + 2

对面数进行归纳

图只有一个面时，也就是图中没有闭环，若有闭环，则必然有两个面了就

考察树

树V = E + 1 公式成立

三角形，节点3， 面2， 边3，成立

假设面数为n时 V + F = E + 2 成立

面数n+1时

在连通图里面必然可以找到一个面与外边的区域相邻

删去相邻的边

面数 - 1

边数 - 1

剩下不变

根据假设，公式成立

则n+1时公式两边都+1，公式成立

命题成立

7. 有路可达

独立集，节点集合，任一两节点不相邻

有向图

  表示a与b相邻，b与a不相邻

证明：G(V, E)有向图，证明G中有一个独立集S(G)，使G中每一个节点都能由S(G)中的点通过长度不超过2的路到达

n <= 3 时， 必然成立

假设节点数

对于节点数为n的有向图

取一个点v

N(v)为所有与v相邻的点的集合 {w |

在G中}

则对于图H = G - v - N(v)

根据假设有S(H)能满足命题要求

1. 若S(G) = S（H） + {v} 是独立集，v又与所有N(v)一步到，则这个图中所有点都可由S（G） 两步内到
2. 若S（H） + {v} 不是独立集，意味着S(H)中必然有一个p，存在边 ,这样p可以经过两步到所有N(v)， 从而S（G） = S（H）, 满足要求

命题成立

8. 格雷码

问题：产生n位元的所有格雷码。

格雷码(Gray Code)是一个数列集合，每个数使用二进位来表示，假设使用n位元来表示每个数字，任两个数之间只有一个位元值不同。

例如以下为3位元的格雷码： 000 001 011 010 110 111 101 100 。

如果要产生n位元的格雷码，那么格雷码的个数为2^n.

假设原始的值从0开始，格雷码产生的规律是：第一步，改变最右边的位元值；第二步，改变右起第一个为1的位元的左边位元；第三步，第四步重复第一步和第二步，直到所有的格雷码产生完毕（换句话说，已经走了(2^n) - 1 步）。

用一个例子来说明：

假设产生3位元的格雷码，原始值位 000

第一步：改变最右边的位元值： 001

第二步：改变右起第一个为1的位元的左边位元： 011

第三步：改变最右边的位元值： 010

第四步：改变右起第一个为1的位元的左边位元： 110

第五步：改变最右边的位元值： 111

第六步：改变右起第一个为1的位元的左边位元： 101

第七步：改变最右边的位元值： 100

 

如果按照这个规则来生成格雷码，是没有问题的，但是这样做太复杂了。如果仔细观察格雷码的结构，我们会有以下发现：

1、除了最高位（左边第一位），格雷码的位元完全上下对称（看下面列表）。比如第一个格雷码与最后一个格雷码对称（除了第一位），第二个格雷码与倒数第二个对称，以此类推。

2、最小的重复单元是 0 , 1。

000

001

011

010

110

111

101

100

所以，在实现的时候，我们完全可以利用递归，在每一层前面加上0或者1，然后就可以列出所有的格雷码。

比如：

第一步：产生 0, 1 两个字符串。

第二步：在第一步的基础上，每一个字符串都加上0和1，但是每次只能加一个，所以得做两次。这样就变成了 00,01,11,10 （注意对称）。

第三步：在第二步的基础上，再给每个字符串都加上0和1，同样，每次只能加一个，这样就变成了 000,001,011,010,110,111,101,100。

好了，这样就把3位元格雷码生成好了。

如果要生成4位元格雷码，我们只需要在3位元格雷码上再加一层0,1就可以了： 0000,0001,0011,0010,0110,0111,0101,0100,1100,1101,1110,1010,0111,1001,1000.

也就是说，n位元格雷码是基于n-1位元格雷码产生的。

9. 无重边的路

 

边数m = 1， 显然成立

假设边数

对于边数m的图

找到O中两个点，必然有一条路

删去这条路，只删边，不删点

原来奇点删路（两条边）后必然度还是奇数

剩下的点还在O中，必然边数

但无法保证剩下的还联通

增强归纳假设

假设边数

这样删掉那条路之后

可以分成多个连通的子图

对于每个子图，边数

这样在加上原来那条路

边数m的图成立

命题成立

常见错误

1. 由于常常要证明的东西是普遍认可的，是熟悉的，所以在证明的时候会偶尔忽略一些条件。如上面的无重边的路问题，很容易忽略删去这条路后原图是否还连通的判断，引发错误。

2. 基础假设需要注意题目的条件，有些会有特殊情况，比如有些n = 1, n = 2 都是对的，n -1 也可以推n的情况，我们会按照数学归纳法判断其正确。但就是特殊情况使得 n = 2 推不了n = 3, 那么整个归纳就错了。

总结

数学归纳法的思想主要就是两种：

1. 知道基础解，然后可以由n的情况推n + 1。

2.知道基础解，知道n+1的情况，并能证明n+1的情况可以由n的情况推出。

计算机科学与数学密切相关，其中的递归便是用的数学归纳法的思想。