归纳法原理与反归纳法

《归纳法原理与反归纳法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、1.5　归纳法原理与反归纳法数学归纳法是中学教学中经常使用的方法．中学教材中的数学归纳法是这样叙述的：如果一个命题与自然数有关，命题对n=1正确；若假设此命题对n－1正确，就能推出命题对n也正确，则命题对所有自然数都正确．通俗的说法：命题对n=1正确，因而命题对n=2也正确，然后命题对n=3也正确，如此类推，命题对所有自然数都正确．对于中学生来说，这样形象地说明就足够了；但是毕竟自然数是无限的，因而上述描述是不够严格的，有了皮阿罗公理后，我们就能给出归纳法的严格证明．定理1.19　如果某个命题Ｔ，它的叙述含有自然数，如果命题Ｔ对n=1是正确的，而且假

2、定如果命题Ｔ对n的正确性就能推出命题Ｔ对n+1也正确，则命题Ｔ对一切自然数都成立．（第一数学归纳法）证明　设Ｍ是使所讨论的例题Ｔ正确的自然数集合，则(1)．设，则命题Ｔ对n正确，这时命题对也正确，即(2)所以由归纳公理Ｄ，Ｍ含有所有自然数，即命题Ｔ对所有自然数都成立．下面我们给出一个应用数学归纳法的命题．例１　求证证明　(1)当n=1时，有所以n=1，公式正确．　　(2)假设当k=n时，公式正确，即那么当k=n＋１时，有所以公式对n+1也正确．在利用数学归纳法证明某些命题时，证明的过程往往归纳到n-1或n-2，而不仅仅是n-1，这时上述归纳法将失败，

3、因而就有了第二数学归纳法．在叙述第二归纳法以前，我们先证明几个与自然数有关的命题．命题１　若，则．证明　因为所以所以命题２　１是自然数中最小的一个．证明　若，则有前元b，所以命题3若，则．（即数与＋１是邻接的两个数，中间没有其他自然数，不存在b，使得．）证明　若,则．因为，所以，即．由上述有关自然数大小的命题，我们得出下面定理，有时也称为最小数原理．定理1.20　自然数的任何非空集合Ａ含有一个最小数，即存在一个数，使得对集合Ａ中任意数b，均有．证明设M是这样的集合：对于M中任意元素，对A中任意元素，均有则M是非空集合．因为，由归纳公理(4)知，一定存

4、在一个元素．但，即，否则由得Ｍ＝Ｎ，这显然不可能．现在我们证明　．因为若，则Ａ中任意元素所以，与矛盾，所以m即为Ａ中最小元素．上述定理也称为最小数原则，有的作者把它当成公理，用它也可以证明数学归纳法，下面我们给出所谓第二数学归纳法．（第二数学归纳法）定理1.21　对于一个与自然数有关的命题Ｔ，若(1)当n=１时命题Ｔ正确；(2)假设命题T对正确，就能推出命题T对正确．则命题T对一切自然数正确．证明　如果命题Ｔ不是对所有自然数都成立，那么使命题不成立的自然数集合Ｍ就是非空集合，由定理1.20，Ｍ中含有一个最小数k，且（∵k=1命题正确），所以对一切,命

5、题T成立，又由(2)推出命题T对k正确．结论矛盾．下面我们给出两个只能应用第二数学归纳法而不能应用第一归纳法解题的例子．例２　已知数列，有且　求证．证明　对n=1，有所以命题对n=1正确．假设命题对正确，则所以命题对n=k正确．由第二数学归纳法本题得证．例３　已知任意自然数均有　（这里）求证证明(1)当n=1时，由，得所以命题对n=1正确．(2)假设对命题正确，这时，当n=k+1时，(1)但是(2)又因为归纳假设对命题正确，所以所以由(1)和(2)式得消去，得解得舍去）所以命题对n=k+1也正确．上边的两个例子，实际上例２命题归结到n-1和n-2，而

6、例３则需要归结到1,2,…k，由此可见，第二数学归纳法的作用是不能由第一归纳法所替代的．现在我们继续讲数学归纳法．当然，归纳并一定从n=1开始，例如例２数列的例子，也可以从某数k开始．数学归纳法还有许多变形，其中著名的有跳跃归纳法、双归纳法、反归纳法以及跷跷板归纳法等，下面我们就逐个介绍这些归纳法．跳跃归纳法　若一个命题Ｔ对自然数,都是正确的；如果由假定命题Ｔ对自然数k正确，就能推出命题Ｔ对自然数正确．则命题对一切自然数都正确．证明　因为任意自然数由于命题对一切中的r都正确，所以命题对都正确，因而对一切n命题都正确．下面我们给出一个应用跳跃归纳法的一

7、个例子．例4　求证用面值3分和5分的邮票可支付任何n(n≥８)分邮资．证明　显然当n=8,n=9,n=10时，可用3分和5分邮票构成上面邮资（n=8时，用一个3分邮票和一个5分邮票，n=9时，用3个3分邮票，n=10时，用2个5分邮票）．下面假定k=n时命题正确，这时对于k=n+3，命题也正确，因为n分可用3分与5分邮票构成，再加上一个3分邮票，就使分邮资可用3分与5分邮票构成．由跳跃归纳法知命题对一切n≥８都成立．下面我们介绍双归纳法，所谓双归纳法是所设命题涉及两个独立的自然数对(m,n),而不是一个单独的自然数n．双归纳法　若命题Ｔ与两个独立的自

8、然数对m与n有关，(1)若命题Ｔ对m=1与n=1是正确的；(2)若从命题Ｔ对自然数对（m,n）正确就能推出该