数学归纳法是一种数学证明方法,通常被用于证明某个给定命题在整个(或者局部)自然数范围内成立,它是以n=1和n=k时命题成立,推出n=k+1时命题也成立的一种方法12。
数学归纳法(Mathematical Induction MI)是一种数学证明方法,通常被用于证明某个给定命题在整个(或者局部)自然数范围内成立。除了自然数以外,广义上的数学归纳法也可以用于证明一般良基结构,例如:集合论中的树。
这种广义的数学归纳法应用于数学逻辑和计算机科学领域,称作结构归纳法。在数论中,数学归纳法是以一种不同的方式来证明任意一个给定的情形都是正确的(第一个,第二个,第三个,一直下去概不例外)的数学定理。
虽然数学归纳法名字中有“归纳”,但是数学归纳法并非不严谨的归纳推理法,它属于完全严谨的演绎推理法。事实上,所有数学证明都是演绎法。
数学归纳法的原理,通常被规定作为自然数公理(参见皮亚诺公理)。但是在另一些公理的基础上,它可以用一些逻辑方法证明。数学归纳法原理可以由下面的良序性质(最小自然数原理)公理可以推出。
发展历程
已知最早的使用数学归纳法的证明出现于Francesco Maurolico的Arithmeticorum libri duo(1575年)。Maurolico利用递推关系巧妙地证明出前n个奇数的总和是n^2,由此总结出了数学归纳法。
最简单和常见的数学归纳法证明方法是证明当n属于所有正整数时一个表达式成立,这种方法是由下面两步组成:递推的基础:证明当n=1时表达式成立。递推的依据:证明如果当n=m时成立,那么当n=m+1时同样成立。