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

[终稿]数学归纳法原理：【第二归纳法】【跳跃归纳法】【反向归纳法】 数学归纳法原理(六种):【第二归纳法】【跳跃归纳法】【反向归纳法】 一行骨牌，如果都充分地靠近在一起(即留有适当间隔)，那么只要推倒第一个，这一行骨牌都会倒塌;竖立的梯子，已知第一级属于可到达的范围，并且任何一级都能到达次一级，那么我们就可以确信能到达梯子的任何一级;一串鞭炮一经点燃，就会炸个不停，直到炸完为止;„„，日常生活中这样的事例还多着呢～ 数学归纳法原理 设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正确 34s同理可推出命题对n=2=8，n=2,„，n=2„都正确(s为任意自然数)，所以命题对无穷多个自然数成立( 设命题对n,k正确，令 则 (容易证明上述是一个恒等式() 由归纳假设命题对n,k正确，所以 所以 即 命题对n =k-1也正确，由反归纳法原理知，命题对一切自然数成立( 由于上述不等式是著名不等式，我们再给出几种证明: mm前已证明，命题对n=2时正确，设n,,，令 这时我们有 m即命题对n,2正确 利用数学归纳法证明 不妨设n个数为，显然当n=1时命题正确( 设命题对正确，令 则 因为，所以 所以命题对n=k+1正确，由第一归纳法知，命题对一切自然数成立( 另一个有趣的证明是由马克罗林给出的，我们知道，若保持和不变，以分别代替和，这时两个数的和仍然是s，但两个数的积却增加了，即 实际上两个数的算术平均值大于几何平均值，只有当两个数相等时才有等号成立( 现在我们变动诸数，但保持它们的和不变，这时乘积 必然在时取极大值(因为若不等于，我们用分别代替与,则 仍然不变，但它们的乘积 却增加了(而当时， 所以n个数的算术平均值大于等于几何平均值( 下面我们给出应用上述不等式的例子( 例, 在体积一定的圆柱形中，求其中表面积最小的一个(即在容积一定罐头中，求表面积最小的一 个)( 解 设圆柱的高为x，底圆半径为y，体积为,,常数，表面积为,，则 其中,为常数，欲求,的极小值( 已知，所以 即 显然只有当时，,取最小值(即当x=2y时，,值最小( 例, 求证在所有具有相同面积的凸四边形中，正方形的周长最短( 证明 用abcd表示四边形的四条边，为a与b的夹角，为c与d的夹角，用,表示四边形的面 积，则 由(2)式得 由(1)式得 其中 再利用半角公式，得 所以 = = = 如令四边形周长，得 因为，所以 要使p最小(A为常数)，只有当上式取等号时(即当 ， 且度，这样的四边形只能是正方形( 6. 最后，我们给出跷跷板归纳法( 有两个与自然数有关的命题A与B，若 nn (1)A成立; 1 (2)假设A成立，就推出B成立，假设B成立就推出A成立( kkkk+1 则对一切自然数n, A与B都成立( nn 这里我们只给出一个例子说明上述归纳法( 例 已知 求证 证明 令 ， (1)当n=1时， 所以A成立( 1 (2) 所以A成立( 2 设A成立，则 k 即,成立( k 若,成立，则 k 即A成立(由跷跷板归纳法知，一切A和B都成立. k+1nn 练习1.5 (1)用数学归纳法证明( (2)求证 ( (3)已知，且，求证 ( 程序原理:【中途点法】【消数法】【消点法】 现在，计算机已极大地普及，相当多的工作都由计算机来处理(要计算机处理某个问题，首先就得将这个问题编成计算机语言——编程(因此，学习计算机常识少不了谈论编程问题(这个常识性问题中也蕴含了我们解数学问题的一个基本原理——程序原理( 这条原理要求做事情应按照一定的程序步骤， 这个原理和切分原理一样，是不需要证明而为人们承认，并得到广泛运用的( 在运用这个原理时，要注意如下几点: (1)分步的有效性(完成这件事的任何一种方法，都要分成几个步骤执行，因此，首先要根据问题的特点确定一个分步，标准不同，分成的步骤也可能不同(各个步骤是相互依存的，必须而且只能连续完成各步骤，这件事才告完成( (2)过程的确定性，把这几个步骤看做一个过程，任何一种解决方法都可归结为这几个步骤形成的过程，而无其他过程( (3)选择的均等性(对于每一个i(i=1，2，„，n-1)，第i步中的每一种方法在其后续步骤(第i+1步)中，均可选用mi+1种方法中的一种( (4)解答的准确性(每一步的解答应尽可能准确，以避免“一着不慎，满盘皆输”( 程序原理及其应用 程序原理I 解决一个问题(或做一件事)，先将待解决的问题适当分解成程序步骤问题，最后按此程序步骤把问题解决，或把一个处理问题的“全过程”恰当地分成几个连接进行的较为简单的“分过程”，最终获得问题的解决， 我们在数学解题中，运用的中途点法、消点法、消数法等都是程序原理I的体现( 中途点法 运用程序原理I解题，可以对某个数学问题在已知与结论之间建立若干小目标或中途点，亦即把原问题分解成一些有层次顺序的小问题，逐个解决这些小问题，逐步达到一个后继一个的小目标或中途点，最后使问题解决， 建立中途小目标，可采用倒推(如例1、例2)、顺推(如例3、例4等)、 两头推(如例5、例6)、猜测或尝试(如例7)等手段( 采用中途点法解题是我们解题的最基本方法之一(它和分解迭加一样，我们早就实践了，在学习中有相当多的数学问题都可采用中途点法解答，下面我们看几个稍难一点儿的例子. 消数法 求解有关代数问题时，先将题设条件中的有关常数巧妙地消去，然后根据消去常数后的式子的特点，分解变形，推演等方式获得所求的结果的方法，我们称为消数法. 消点法 在研究几何定理的机器证明中，张景中院士以他多年来发展的几何新方法(面积法)为基本工具，提出了消点思想，和周咸青、高小山合作，于1992年突破了这项难题，实现了几何定理可读性证明的自动生成(这一新方法既不以坐标为基础，也不同于传统的综合方法，而是一个以几何不变量为工具，把几何、代数逻辑和人工智能方法结合起来所形成的开发系统(它选择几个基本的几何不变量和一套作图规则并且建立一系列与这些不变量和作图规则有关的消点公式，当命题的前提以作图语句的形式输入时，程序可调用适当的消点公式把结论中的约束关系逐个消去，最后水落石出，消点的过程记录与消点公式相结合，就是一个具有几何意义的证明过程. 基于此法所编的程序，已在微机上对数以百计的困难的几何定理完全自动生成了简短的可读证明，其效率比其他方法高得多，这一成果被国际同行誉为使计算机能像处理算术那样处理几何的发展道路上的里程碑，是自动推理领域三十年来最重要的成果. 更值得一提的是，这种方法也可以不用计算机而由人用笔在纸上执行(这种方法我们称为证明几何问题的消点法，消点法把证明与作图联系起来，把几何推理与代数演算联系起来，使几何解题的逻辑性更强了，它结束了两千年来几何证题无定法的局面，把初等几何解题法从只运用四则运算的层次推进到代数方法的阶段(从此，几何证题有了以不变应万变的程式(