数学归纳法的变式及应用

数学归纳法的几种变式及其应用专业：数学与应用数学姓名：导师：目录1.引言2.数学归纳法3.数学归纳法的变式4.数学归纳法和反证法的关系5.关于数学归纳法的若干说明6.总结1.引言数学归纳法是一种完全归纳法。它是一种常用于证明与正整数集有关命题的重要论证方法，在几何证明和代数证明中都有着广泛的应用。2.数学归纳法第一类数学归纳法（数学归纳法）第一类数学归纳法的基本形式为：设是一个关于自然数n的命题，如果pn(1)成立；1p(2)假设成立，则也成立；pk1pkpn那么，对任意自然数n都成立。第二类数学归纳法第二类数学归纳法又称串值归纳法，它的基本形式为：设是一个关于自然数n的命题，如果pn(1)成立；1p(2)假设对于所有适合nk的正整数n成立，则也成立；pnpk那么，对任意自然数n都成立。pn例2.3.2证明可以仅用4分和5分邮票来组成等于和超过12分的每种邮资。12,13,14,15pppp(1)当n=12,13,14,15时，命题为真。票加上1个4分邮票就可以了。为了组成n+1分邮资，用组成n-3分邮资的邮即可以用4分和5分邮票来组成k（）分邮资。(2)对于任意自然数n15,假定命题为真pn15kn两类数学归纳法是等价的第一数学归纳法和第二数学归纳法是等价的，即用第一数学归纳法证明的可以用第二数学归纳法证明，反之亦然。pn3.数学归纳法的变式1跳跃归纳法跳跃归纳法的基本形式为：那么，对任意自然数都成立。pn数k+l正确；(2)假设对于自然数k正确，就能推出命题对自然(1)成立；12pppl、、设是一个关于自然数n的命题，如果pn反归纳法的基本形式为：设是一个关于自然数n的命题，如果(1)对无穷多个自然数成立；(2)假设对于自然数k正确，就能推出命题对自然数k-1正确；那么，对任意自然数n都成立。pnpnpnpn2反归纳法（倒推归纳法）例求证n个正实数的算术平均值大于或等于这n个数的几何平均值，即nnnaaanaaa2121证明：(1)当n=2时，因此命题对n=2正确。当n=4时，因此命题对n=4正确。同理可推出命题对都正确（s为任意自然数）。21212aaaa224341234121234()()()224aaaaaaaaaaaa342,2,,2snnn(2)设命题对n=k正确，令则由归纳假设命题对n=k正确，所以所以即1,121121kaaaskaaaskkkkksaaaskkk11211121111211S()kkkkkkkaaasaaask11121Skkkaaa11211211kkkaaakaaa命题对n=k-1也正确，由反归纳法原理知，命题对一切自然数成立。第一类数学归纳法的关键是：由成立往后推出也成立；而反归纳法的关键恰是：由成立往前推出成立。pk1pkpk1pk双归纳法的基本形式为：设命题P与两个独立的自然数对m与n有关，若(1)命题P对m=1与n=1是正确的；(2)从命题对自然数对（m,n）正确就能推出该命题对自然数对（m+1,n）正确，和对自然数对（m,n+1）也正确；则命题P对一切自然数对（m,n）都正确。3双归纳法（二元归纳法）跷跷板归纳法的基本形式为：有两个命题,如果(1)正确；(2)假设正确，那么也是正确的；(3)假设正确，那么也是正确的；那么，对于任意自然数n,命题都是正确的。,nnAB1A1kAkAkBkB,nnAB4跷跷板归纳法与螺旋式上升归纳法例已知数列1，3，7，12，19，27，37，48，61……设为其第n项，为其前n项的和，其中求证：nSna22213,311llalall2221211431,431.22llSlllSlll证明：令为；为为nA22114312nSnnnnB2214312nSnnn(1)，即是正确的。11S1A(2)假设那么即，假设是正确的，那么也正确。22114312kSkkk222221211431343122kkkSSakkkkkkkkAkB即，假设是正确的，则也正确。kB1kA(3)假设，那么2214312kSkkk22212212322114313114316122211149721452141311222kkkSSakkkkkkkkkkkkkkkkkkk因此，对任何自然数都是正确的。,nnAB说明：作为“跷跷板归纳法”的推广，还可能要使用若干结论螺旋式上升的证明方法，这种方法的基本形式为：有五个命题，如果(1)是正确的；(2)那么，这五个命题都是正确的。,,,,nnnnnABCDE1A1,,,,kkkkkkkkkkABBCCDDEEA4数学归纳法和反证法的关系凡是用数学归纳法证明的命题都可以用反证法来证明，因而数学归纳法在使用上可以用反证法来代替，反之不然。pn每一种形式的数学归纳法都有两个步骤，第一步是验证步骤，第二步是归纳步骤。这两步相辅相成，缺一不可。下面这个例子就是很好的说明。5.关于数学归纳法的若干说明例二项式曾引起数学家们的极大兴趣，最使数学家们感性趣的是把它分解为具有整系数因子的乘积。1nx对许许多多特殊n的值，考查的分解式。数学家们发现：在分解式中，x的各次幂的所有系数的绝对值都不超过1。实际上，1nx23242543262211,111,111,1111,111,11111,xxxxxxxxxxxxxxxxxxxxxxxxxx48474643424039363534333231282624222017161514413127519862221.xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx这表明它不具有所说的性质。所有次数小于105的二项式都具有所说的性质，但当n=105时，的一个分解因子是1051x许多证明起来比较复杂的数学命题与公式，利用数学归纳法很容易就可以证明出来。通过数学归纳法，我们可以从个别事实中找出一般规律性。正如华罗庚先生在其《数学归纳法》一书中指出的那样：“数学归纳法正是体现了人的认识从有限到无限的飞跃。”总结