数学归纳法在离散数学中的应用

《数学归纳法在离散数学中的应用》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数学归纳法在离散数学中的应用在由一系列有限的特殊事例得出一般性结论的推理方法称为归纳法。而数学归纳法则是用于证明与自然数n有关的结论的归纳法：如果我们能够证明当n=1时结论是成立的，而且我们能用相同的方法由n=1命题成立证得n=2命题也成立；由n=2命题成立证得n=3成立；由n=3命题成立证得n=4成立…而且这个过程显然可以无穷进行下去。则我们就断言对于所有自然数n命题都是成立的。数学归纳法的一般形式为，关键是归纳：初始步）：先证n＝1时，结论成立；归纳步)：再证若假设对自然数n＝k结论成立（或者对所有小于等于n的自然数k结论都成立），则对下一个自然数n＝k+1结论也成立；结论

2、）：根据初始步和归纳步的证明得出结论对所有自然数都成立。当结论与多个自然数有关时这样一类题目的时候，要注意的一点就是对所要进行归纳的自然数的选择。　例1、对群的任意元素a,b，及任何正整数m，n,a*a=a问题解析：这是自然数有关的结论。但这里涉及到两个自然数，但由元素的幂的定义以及m和n的作用的对称性，故只要任意选择其中一个即可。证明：用数学归纳法对n进行归纳证明。对任何正整数m，当n=0时，有a*a=a*a=a*e=a。故结论成立。假设当n=k时，a*a=a。则当n=k+1时，由*满足结合律、元素的幂的定义及归纳假设a*a=a*(a*a)=(a*a)*a=a*a=

3、a，即结论对n=k+1也成立。故对任何正整数m,n,ea*a=a例2、设d,d,…,d为n个正整数，n≥2,并且=2n-2。证明：存在n个顶点的树T使它的顶点度数分别是d,d,…,d。问题解析：在这个问题中，结论显然与顶点的个数n有关。故对n进行归纳，先构造出具有2个顶点满足条件的树。然后假设已经构造出具有k个顶点的树，由此构造出具有k+1个顶点的树。数学归纳法成功的关键是如何从k+1个顶点的树找出一个叶节点，将该叶节点从树上删去后，得到的图仍是一棵具有同样性质但只有k个顶点的树。证明：用数学归纳法对顶点数n进行归纳。当n=2时，由于d,d都是正整数，且d+d=2，故d=d=1

4、。显然具有2个顶点的树的度数都是1。假设当n=k(k≥2)时，命题成立，即对任k个和为2k-2的正整数，总有k个顶点的树，使它的k个顶点的度数分别是这k个正整数。现在考虑n=k+1的情形。设d,d,…,d为满足=2k的k+1个正整数，则d,d,…,d中必定有一个为1（否则d,d,…,d都大于等于2，从而2(k+1)>2k，从而与已知条件=2k矛盾）。另外d,d,…,d中必定有一个大于1（否则d,d,…,d都等于1，从而=k+1<2k，从而也与已知条件=2k矛盾）。不妨设d=1且d2。从而d-1,d,…,d是k个正整数，且因为=2且d=1，所以d-1,d,…,d的和为2k-2。根

5、据归纳假设，存在一棵有k个节点的树T，其节点的度数分别是d-1,d,…,d。设T中度数为d-1的顶点是u，我们现在在T上添加顶点v，并在顶点v和u之间增加一条边，得到T，则T仍为树，且u的度数从d-1变成了d，v的度数为1，其余各顶点度数不变。则这样得到的树T有k+1个顶点且各顶点的度数分别为d（=1）,d,…,d。从而命题得证。例3、设有n个顶点m条边的无向连通图T满足m=n-1，则T无简单回路。问题解析：这实际上是无向树的一个判定条件。在这个问题中，结论显然与两个自然数：顶点数n和边数m有关。但是由条件m=n-1，m和n是相互信赖的。但从图论的相关知识判断（如欧拉握手定理等

6、），对n进行归纳比较简便。故先验证2个顶点满足题目条件的图。然后假设对具有k个顶点的题设的图，结论是成立的。考虑具有k+1个顶点的满足题设的图时，数学归纳法成功的关键是如何从k+1个顶点的图找出一个叶节点，将该叶节点从该图中删除后，得到的图仍是一个满足题设但只有k个顶点的图。证明：先证T无简单回路，为此用数学归纳法对顶点n进行归纳。当n=2时显然T无简单回路，因这时m=n–1=1，T中只有一条边。假设当顶点数为k（3）时，满足题目条件的图无简单回路。下面考虑顶点数为k+1时满足题目条件的图T。因为T有k条边，由欧拉握手定理知，T中所有顶点度数之和是2k。但由于T有k+1个顶点且

7、T是连通图，故T至少有一个度数为1的顶点，将这个顶点从T上去掉得到一个新图T。显然T仍是连通图，且它有k-1条边，k个顶点。故由由归纳假设得T无简单回路。由于T和T的关系可知，故T也没有简单回路。从而满足题目条件的图T是没有简单回路的。