数学归纳法

（mathematical induction）亦称“递归证法”。完全归纳法的一种。数学上证明命题的一种方法。由于自然数具有这样一个重要性质：任意一个自然数的集合，如果包含1；并且假设包含k，也一定包含k的后继数k+1，那么这个集合包含所有的自然数。根据这一性质，为了证明与自然数n有关的一个命题，如果能证明（1）当n=1时命题成立；（2）当n=k时命题成立的条件下，如n=k+1命题也成立，那么，我们就能由n=1时命题成立，推出n=1+1=2也成立；由n =2时命题成立，推出n=2+1=3时也成立……这样，则对于任意自然数n命题都成立。例如，由于1=12，又在1 +3+5+…+（2k-1） =k2的假定下，得到1 +3+5+…+ （2k-1） +（2k+1） =（k+1）2，所以最初n个奇数的和等于n2。一般说来，对于一些可以递推的有关自然数的命题，都可以用这种数学归纳法来证明。应用这种归纳法证题时，主要有以下两个步骤。第一步：证明当n=1时命题成立；第二步：假设当n=k时命题成立，证明n=k+1时命题也成立。两个步骤缺一不可。第一步是奠基步骤，缺少它递进就没有基础；第二步是归纳步骤，缺少它递进就没有根据。前者为后者的假定提供了初始的实际根据，在此基础上，才能经第二步逐个递推，作出“命题对任意自然数都成立”的结论。无穷归纳（infinite induction）归纳推理的一种极端形式。作为结论的全称命题是通过包括该类的一切个别事例的无穷个前提而归纳得出的。比如，1 ×0=0×1；1 ×1=1 ×1；1 ×2=2×1；1 ×3=3 ×1；1 ×4=4×1；1 ×5=5×1；1 ×6=6×1；……因此，等式1 ×x=x × 1适用于任何一个自然数（即非负整数）x。其推理图式可以表述如下：因此，所有自然数都具有性质S。这种推理也可表示为：其中，横线上者表示前提，下者表示结论。其结论的全称性就表现在结论S（x）中含有表示变量的x，它可以取代任何一个自然数为值。但要列出无穷个前提在事实上是不可能的，因此，无穷归纳的纯粹形式在思维和论证的实际过程中是不会碰到的。因此，在科学思维的实践中，无穷归纳或者为不完全归纳所代替（这时，作为前提而列举的就不是其全称性结论所需要的全部个别事例，而只是一部分事例），或者就为数学归纳法所代替。无穷归纳在一系列理论结构，特别是在数学基础和数理逻辑中有着为其他归纳形式所无法代替的作用。