数学归纳法原理：【第二归纳法】【跳跃归纳法】【反向归纳法】

数学归纳法原理(六种)：【第二归纳法】【跳跃归纳法】【反向归纳法】一行骨牌，如果都充分地靠近在一起（即留有适当间隔），那么只要推倒第一个，这一行骨牌都会倒塌；竖立的梯子，已知第一级属于可到达的范围，并且任何一级都能到达次一级，那么我们就可以确信能到达梯子的任何一级；一串鞭炮一经点燃，就会炸个不停，直到炸完为止；……，日常生活中这样的事例还多着呢！数学归纳法原理设P(n)是与自然数n有关的命题．若(I)命题P(1)成立；(Ⅱ)对所有的自然数k，若P(k)成立，推得P(k+1)也成立.由（I）、(Ⅱ)可知命题P(n)对一切自然数n成立．我们将在“最小数原理”一章中介绍它的证明，运用数学归纳法原理证题的方法，是中学数学中的一个重要的方法，它是一种递推的方法，它与归纳法有着本质的不同．由一系列有限的特殊事例得出一般结论的推理方法，通常叫做归纳法，用归纳法可以帮助我们从具体事例中发现一般规律，但是，仅根据一系列有限的特殊事例得出的一般结论的真假性还不能肯定，这就需要采用数学归纳法证明它的正确性．一个与自然数n有关的命题P(n)，常常可以用数学归纳法予以证明，证明的步骤为：(I)验证当n取第1个值no时，命题P(no)成立，这一步称为初始验证步．(Ⅱ)假设当n=k(k∈N，后≥no)时命题P(k)成立，由此推得命题P(k+1)成立．这一步称为归纳论证步．(Ⅲ)下结论，根据(I)、(Ⅱ)或由数学归纳法原理断定，对任何自然数(n≥no)命题P(n)成立．这一步称为归纳断言步，为了运用好数学归纳法原理，下面从有关注意事项与技巧及运用递推思想解题等几个方面作点介绍．运用数学归纳法证题时应注意的事项与技巧三个步骤缺一不可第一步是递推的基础，第二步是递推的依据，第三步是递推的过程与结论．三步缺一不可．数学归纳法的其他几种形式还有：第二数学归纳法；跳跃数学归纳法；倒推数学归纳法（反向归纳法）；分段数学归纳法二元有限数学归纳法；双向数学归纳法；跷跷板数学归纳法；同步数学归纳法等。1.5归纳法原理与反归纳法数学归纳法是中学教学中经常使用的方法．中学教材中的数学归纳法是这样叙述的：如果一个命题与自然数有关，命题对n=1正确；若假设此命题对n－1正确，就能推出命题对n也正确，则命题对所有自然数都正确．通俗的说法：命题对n=1正确，因而命题对n=2也正确，然后命题对n=3也正确，如此类推，命题对所有自然数都正确．对于中学生来说，这样形象地说明就足够了；但是毕竟自然数是无限的，因而上述描述是不够严格的，有了皮阿罗公理后，我们就能给出归纳法的严格证明．1.第一数学归纳定理1.19如果某个命题Ｔ，它的叙述含有自然数，如果命题Ｔ对n=1是正确的，而且假定如果命题Ｔ对n的正确性就能推出命题Ｔ对n+1也正确，则命题Ｔ对一切自然数都成立．（第一数学归纳）证明设Ｍ是使所讨论的例题Ｔ正确的自然数集合，则(1)．设，则命题Ｔ对n正确，这时命题对也正确，即(2)所以由归纳公理Ｄ，Ｍ含有所有自然数，即命题Ｔ对所有自然数都成立．下面我们给出一个应用数学归纳法的命题．例１求证证明(1)当n=1时，有所以n=1，公式正确．(2)假设当k=n时，公式正确，即那么当k=n＋１时，有所以公式对n+1也正确．在利用数学归纳法证明某些命题时，证明的过程往往归纳到n-1或n-2，而不仅仅是n-1，这时上述归纳法将失败，因而就有了第二数学归纳法．在叙述第二归纳法以前，我们先证明几个与自然数有关的命题．2.第二数学归纳法命题１若，则．证明因为所以所以命题２１是自然数中最小的一个．证明若，则有前元b，所以命题3若，则．（即数与＋１是邻接的两个数，中间没有其他自然数，不存在b，使得．）证明若,则．因为，所以，即．由上述有关自然数大小的命题，我们得出下面定理，有时也称为最小数原理．定理1.20自然数的任何非空集合Ａ含有一个最小数，即存在一个数，使得对集合Ａ中任意数b，均有．证明设M是这样的集合：对于M中任意元素，对A中任意元素，均有则M是非空集合．因为，由归纳公理(4)知，一定存在一个元素．但，即，否则由得Ｍ＝Ｎ，这显然不可能．现在我们证明．因为若，则Ａ中任意元素所以，与矛盾，所以m即为Ａ中最小元素．上述定理也称为最小数原则，有的作者把它当成公理，用它也可以证明数学归纳法，下面我们给出所谓第二数学归纳法．（第二数学归纳法）定理1.21对于一个与自然数有关的命题Ｔ，若(1)当n=１时命题Ｔ正确；(2)假设命题T对正确，就能推出命题T对正确．则命题T对一切自然数正确．证明如果命题Ｔ不是对所有自然数都成立，那么使命题不成立的自然数集合Ｍ就是非空集合，由定理1.20，Ｍ中含有一个最小数k，且（∵k=1命题正确），所以对一切,命题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，而例３则需要归结到1,2,…k，由此可见，第二数学归纳法的作用是不能由第一归纳法所替代的．现在我们继续讲数学归纳法．当然，归纳并一定从n=1开始，例如例２数列的例子，也可以从某数k开始．数学归纳法还有许多变形，其中著名的有跳跃归纳法、双归纳法、反归纳法以及跷跷板归纳法等，下面我们就逐个介绍这些归纳法．3.跳跃归纳法若一个命题Ｔ对自然数,都是正确的；如果由假定命题Ｔ对自然数k正确，就能推出命题Ｔ对自然数正确．则命题对一切自然数都正确．证明因为任意自然数由于命题对一切中的r都正确，所以命题对都正确，因而对一切n命题都正确．下面我们给出一个应用跳跃归纳法的一个例子．例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．4.双归纳法若命题Ｔ与两个独立的自然数对m与n有关，(1)若命题Ｔ对m=1与n=1是正确的；(2)若从命题Ｔ对自然数对（m,n）正确就能推出该命题对自然数对（m+1,n）正确，和对自然数对（m,n+1）也正确．则命题Ｔ对一切自然数对（m,n）都正确．关于双归纳法的合理性证明我们不予说明，只给出一个例子．例５求证对任意自然数m与n均有证明(1)当时，命题显然正确，即(2)设命题对自然数对m与n正确，即这时即命题对数对（m+1,n）正确；另一方面即命题对数对(m,n+1)也正确，由双归纳法知，命题对一切自然数对(m,n)都成立．5.反归纳法若一个与自然数有关的命题Ｔ，如果(1)命题Ｔ对无穷多个自然数成立；(2)假设命题Ｔ对n=k正确，就能推出命题Ｔ对n=k-1正确．则命题Ｔ对一切自然数都成立；上述归纳法称为反归纳法，它的合理性我们做如下简短说明：设Ｍ是使命题Ｔ不正确的自然数，如果Ｍ是非空集合，则Ｍ中存在最小数m，使得命题Ｔ对k=m不正确；由于命题对无穷多个自然数正确，所以存在一个，且命题T对正确；由于命题T对m不正确，所以命题对也不正确，否则由命题T对正确就推出命题T对m正确．矛盾！这样，命题Ｔ对m+2也不正确，经过次递推后，可得命题Ｔ对也不正确．这与已知矛盾，所以Ｍ是空集合．反归纳法又称倒推归纳法，法国数学家柯西（1789-1857）首次用它证明了n个数的算术平均值大于等于这n个数的几何平均值．例6求证n个正实数的算术平均值大于或等于这n个数的几何平均值，即证明当n=2时，因此命题对n=2正确．当n=4时，因此命题对n=4正确同理可推出命题对n=23=8，n=24,…，n=2s…都正确（s为任意自然数），所以命题对无穷多个自然数成立．设命题对n＝k正确，令则（容易证明上述是一个恒等式．）由归纳假设命题对n＝k正确，所以所以即命题对n=k-1也正确，由反归纳法原理知，命题对一切自然数成立．由于上述不等式是著名不等式，我们再给出几种证明：前已证明，命题对n=2m时正确，设n＜２m，令这时我们有即命题对n＜2m正确利用数学归纳法证明不妨设n个数为，显然当n=1时命题正确．设命题对正确，令则因为，所以所以命题对n=k+1正确，由第一归纳法知，命题对一切自然数成立．另一个有趣的证明是由马克罗林给出的，我们知道，若保持和不变，以分别代替和，这时两个数的和仍然是s，但两个数的积却增加了，即实际上两个数的算术平均值大于几何平均值，只有当两个数相等时才有等号成立．现在我们变动诸数，但保持它们的和不变，这时乘积必然在时取极大值．因为若不等于，我们用分别代替与,则仍然不变，但它们的乘积却增加了．而当时，所以n个数的算术平均值大于等于几何平均值．下面我们给出应用上述不等式的例子．例７在体积一定的圆柱形中，求其中表面积最小的一个（即在容积一定罐头中，求表面积最小的一个）．解设圆柱的高为x，底圆半径为y，体积为Ｖ＝常数，表面积为Ｓ，则其中Ｖ为常数，欲求Ｓ的极小值．已知，所以即显然只有当时，Ｓ取最小值．即当x=2y时，Ｓ值最小．例８求证在所有具有相同面积的凸四边形中，正方形的周长最短．证明用abcd表示四边形的四条边，为a与b的夹角，为c与d的夹角，用Ａ表示四边形的面积，则由（2）式得由（1）式得其中再利用半角公式，得所以===如令四边形周长，得因为，所以要使p最小（A为常数），只有当上式取等号时．即当，且度，这样的四边形只能是正方形．6.最后，我们给出跷跷板归纳法．有两个与自然数有关的命题An与Bn，若(1)A1成立；(2)假设Ak成立，就推出Bk成立，假设Bk成立就推出Ak+1成立．则对一切自然数n,An与Bn都成立．这里我们只给出一个例子说明上述归纳法．例已知求证证明令，(1)当n=1时，所以A1成立．(2)所以A2成立．设Ak成立，则即Ｂk成立．若Ｂk成立，则即Ak+1成立．由跷跷板归纳法知，一切An和Bn都成立.练习1.5(1)用数学归纳法证明．(2)求证．(3)已知，且，求证．程序原理：【中途点法】【消数法】【消点法】现在，计算机已极大地普及，相当多的工作都由计算机来处理．要计算机处理某个问题，首先就得将这个问题编成计算机语言——编程．因此，学习计算机常识少不了谈论编程问题．这个常识性问题中也蕴含了我们解数学问题的一个基本原理——程序原理．这条原理要求做事情应按照一定的程序步骤，这个原理和切分原理一样，是不需要证明而为人们承认，并得到广泛运用的．在运用这个原理时，要注意如下几点：(1)分步的有效性．完成这件事的任何一种方法，都要分成几个步骤执行，因此，首先要根据问题的特点确定一个分步标准，标准不同，分成的步骤也可能不同．各个步骤是相互依存的，必须而且只能连续完成各步骤，这件事才告完成．(2)过程的确定性，把这几个步骤看做一个过程，任何一种解决方法都可归结为这几个步骤形成的过程，而无其他过程．(3)选择的均等性．对于每一个i（i=1，2，…，n-1），第i步中的每一种方法在其后续步骤（第i+1步）中，均可选用mi+1种方法中的一种．(4)解答的准确性．每一步的解答应尽可能准确，以避免“一着不慎，满盘皆输”．程序原理及其应用程序原理I解决一个问题（或做一件事），先将待解决的问题适当分解成程序步骤问题，最后按此程序步骤把问题解决，或把一个处理问题的“全过程”恰当地分成几个连接进行的较为简单的“分过程”，最终获得问题