数学归纳法查看源代码讨论查看历史
| 数学归纳法 |
数学归纳法（Mathematical Induction, MI）是一种数学证明方法，通常被用于证明某个给定命题在整个（或者局部）自然数范围内成立。除了自然数以外，广义上的数学归纳法也可以用于证明一般良基结构，例如：集合论中的树。这种广义的数学归纳法应用于数学逻辑和计算机科学领域，称作结构归纳法。
简介
数学归纳法（Mathematical Induction, MI）是一种数学证明方法，通常被用于证明某个给定命题在整个（或者局部）自然数范围内成立。除了自然数以外，广义上的数学归纳法也可以用于证明一般良基结构，例如：集合论中的树。这种广义的数学归纳法应用于数学逻辑和计算机科学领域，称作结构归纳法。在数论中，数学归纳法是以一种不同的方式来证明任意一个给定的情形都是正确的（第一个,第二个，第三个，一直下去概不例外）的数学定理。虽然数学归纳法名字中有“归纳”，但是数学归纳法并非不严谨的归纳推理法，它属于完全严谨的演绎推理法。事实上，所有数学证明都是演绎法。
评价
数学归纳法的原理，通常被规定作为自然数公理（参见皮亚诺公理）。但是在另一些公理的基础上，它可以用一些逻辑方法证明。数学归纳法原理可以由下面的良序性质（最小自然数原理）公理可以推出：自然数集是良序的。（每个非空的正整数集合都有一个最小的元素）比如{1, 2, 3 , 4, 5}这个正整数集合中有最小的数——1.下面我们将通过这个性质来证明数学归纳法：对于一个已经完成上述两步证明的数学命题，我们假设它并不是对于所有的正整数都成立。对于那些不成立的数所构成的集合S，其中必定有一个最小的元素k。（1是不属于集合S的，所以k>1）k已经是集合S中的最小元素了，所以k-1是不属于S，这意味着k-1对于命题而言是成立的——既然对于k-1成立，那么也对k也应该成立，这与我们完成的第二步骤矛盾。所以这个完成两个步骤的命题能够对所有n都成立。注意到有些其它的公理确实是数学归纳法原理的可选的公理化形式。更确切地说，两者是等价的。已知最早的使用数学归纳法的证明出现于Francesco Maurolico的Arithmeticorum libri duo（1575年）。Maurolico利用递推关系巧妙地证明出前n个奇数的总和是n^2，由此总结出了数学归纳法。最简单和常见的数学归纳法证明方法是证明当n属于所有正整数时一个表达式成立，这种方法是由下面两步组成：递推的基础：证明当n=1时表达式成立。递推的依据：证明如果当n=m时成立，那么当n=m+1时同样成立。这种方法的原理在于第一步证明起始值在表达式中是成立的，然后证明一个值到下一个值的证明过程是有效的。如果这两步都被证明了，那么任何一个值的证明都可以被包含在重复不断进行的过程中。[1]