数学归纳原理和最小数原理的等价性证明_高等数学定理证明总结
数学归纳原理和最小数原理的等价性证明由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“高等数学定理证明总结”。
数学归纳原理和最小数原理的等价性证明
这两个原理都是自然数公理系统中最基本的原理，人们常常用最小数原理证明数学归纳原理。我发现用数学归纳原理也可以证最小数原理。所谓的最小数原理是指：自然数集合的任意非空子集必有最小元素。一：用数学归纳原理证最小数原理。当自然数的非空子集只含一个元素时，这个元素就是最小元素。设n
元集有最小元素，对于n+1 元集，新加入的元素与n元集中的最小数比较，若新加入的元素不大于该最小数，则新加入的元素为最小数，否则，原来的n元集中的最小数仍是n+1元集的最小数。由数学归纳原理，含任意个自然数数目的自
然数子集都有最小数。得证。
二：用最小数原理证数学归纳原理：p(o)成立，且p(n)成立可导出p(n+1)成立，则对于一切自然数n,p(n)成立。否则，若对于若干个（可能有限个，也可能无限个）自然数m1,……mi……(i≥1）使命题不成立，由最小数原理，这若干个自然数有最小数记为w，而且，w一定是正数，那么，就一定存在唯一的自然数b,b+1=w.b不属于这个使命题不成立的元素组成的集合，因为b比最小数还小。则p(b)是成立的，由规则，p(b+1)也成立即p(w)成立。矛盾。故对于一切自然数n,p(n)成立。证毕。
其实以上发现也没啥大不了的，很直观浅显。这两个原理的等价性得证后，两者中的任意一条都可以作为皮亚杰五条公理中的一条吗？不行！因为最小数原理中的小于最开始还是没有定义的！。
还有，该等价关系非我第一次发现，由于其十分简单，在我发现等价性后，我在华罗庚的《数学归纳法》
最后找到了同样的结论。
归纳原理和数学归纳法
1．数学归纳法的理论依据
归纳法和演绎法都是重要的数学方法．归纳法中的完全归纳法和演绎法都是逻辑方法；不完全归纳法是非逻辑方法，只适用于数学发现思维，不适用数学严格证明．
数学归纳法既不是归纳法，也不是演绎法，是一种递归推理，其理论依据是下列佩亚诺公理Ⅰ—Ⅴ中的归纳公理：
Ⅰ．存在一个自然数0∈N；
Ⅱ．每个自然数a有一个后继元素a′，如果a′是a的后继元素，则a叫做a′的生成元素；
Ⅲ．自然数0无生成元素；
Ⅳ．如果a′=b′，则a=b；
Ⅴ．(归纳公理)自然数集N的每个子集合M，如果M含有0，并且含有M内每个元素的后继元素，则M＝N
自然数就是满足上述佩亚诺公理的集合N中的元素．关于自然数的所有性质都是这些公理的直接推论．由佩亚诺公理可知，0是自然数关于“后继”的起始元素，如果记0′＝1，1′=2，2′=3，„，n′=n＋1，„，则
N=｛0，1，2，„，n，„｝
由佩亚诺公理所定义的自然数与前面由集合所定义的自然数，在本质上是一致的．90年代以前的中学数学教材中，将自然数的起始元素视作1，则自然数集即为正整数集．现在已统一采取上面的记法，将0作为第一个自然数．
定理1(最小数原理)自然数集N的任一非空子集A都有最小数．
这本是自然数集N关于序关系∈(＜)为良序集的定义．现在用归纳公理来证明．
证 设M是不大于A中任何数的所有自然数的集合，即
M=｛n｜n∈N且n≤m，对任意m∈A｝
由于A非空，至少有一自然数a∈A，而 a＋1(＞a)不在M中．所
然，就有
1° 0∈M(0不大于任一自然数)；
2° 若m∈M，则m＋1∈M．
根据归纳公理，应有M＝N．此与M≠N相矛盾．
这个自然数m0就是集合A的最小数．因为对任何a∈A，都有m0于是m0＋1∈M，这又与m0的选取相矛盾．
反之，利用最小数原理也可以证明归纳公理．因此，最小数原理与归纳公理是等价的．
定理2(数学归纳法原理)一个与自然数相关的命题T(n)，如果
1° T(n0)(n0≥0)为真；
2° 假设T(n)(n≥n0)为真，则可以推出T(n＋1)也为真．
那么，对所有大于等于n0的自然数n，命题T(n)为真．
证 用反证法．若命题T(n)不是对所有自然数n为真，则
M=｛m｜m∈N，m≥n0且T(m)不真｝
非空．根据定理1，M中有最小数m0．由1°，m0＞n0，从而m0－1≥n0且T(m0-1)为真．由2°，取n=m0-1即知T(m0)为真．此与T(m0)不真相矛盾．从而证明了定理2．
在具体运用数学归纳法进行数学证明时，有多种不同形式．运用定理2中两个步骤进行证明的，为Ⅰ型数学归纳法．经常使用的还有Ⅱ型数学归纳法，Ⅱ型数学归纳法是：
如果命题T(n)满足
1° 对某一自然数n0≥0，T(n0)为真；
2° 假设对n0≤k≤n的k，T(k)为真，则可以推出 T(n＋1)也真． 那么．对所有大于等于n0的自然数，命题T(n)都真．
意a∈A，定理3 Ⅰ型数学归纳法和Ⅱ型数学归纳法等价．
证 假设命题 T(n)对n=n0为真，于是只须证明“由T(n)(n≥n0)为真，可以推出T(n＋1)也为真”的充要条件为“由T(k)(n0≤k≤n)为真，可以推出T(n+1)也为真．”
1° 充分性
若“由T(n)(n≥n0)为真，可以推出 T(n＋1)也为真”，则对n0≤k≤n，T(k)为真，特别 T(n)为真，因此 T(n＋1)也为真．
2° 必要性
用反证法．若“由 T(k)(n0≤k≤n)为真，可以推出 T(n＋1)也为真”，但并非对所有大于等于n0的自然数n，由T(n)为真，可以推出 T(n＋1)也为真，则 M=｛m｜m∈N，m≥n0且由T(n)为真推不出T(n＋1)也为真｝非空．由定理1，M中有最小数m0，且对n0≤k＜m0的k，由T(k)为真，可以推出T(k＋1)也为真．特别由 T(n0)为真可知 T(n0+1)为真，由T(n0＋1)为真可知 T(n0＋2)为真，„„，由T(m0－1)为真可知 T(m0)为真．现已知T(n0)为真，所以T(n0)，T(n0+1)，„，T(m0)都为真，由此可知 T(m0＋1)也为真，所以由 T(m0)为真推出了T(m0＋1)也为真．这与m0的选取矛盾．
由定理3可知，Ⅱ型数学归纳法也是合理的推理方法．
2．数学归纳法在应用中要注意的问题
第一，证明的两个步骤缺一不可第一步是归纳的基础，第二步是归纳的传递．尤其是不可忽视第一步的验证．
例1试证
1＋3＋5＋„＋(2n＋1)＝(n＋1)2＋1
证 假设当n=k时公式成立，则
1＋3＋5＋„＋(2n-1)＋(2n+1)
＝［1＋3＋5＋„＋(2n-1)］＋(2n＋1)
＝n2＋1＋2n＋1＝(n＋1)2＋1
完成了数学归纳法的第二步，但结论显然是错误的．为什么？因为缺少第一步．事实上，当n=0时，公式不成立．
如果缺了第二步，则不论对多少个自然数来验证命题T(n)的正确性，都不能肯定命题对所有自然数都正确．例如，哥德巴赫猜想“任何不小于6的偶数都可以表成两个奇素数之和”，虽然对大量偶数进行了具体验证，但因缺少第二步归纳传递，所以仍只停留在归纳的第一步上．它至今仍只是个猜想而已．
第二，第二步在证明T(n＋1)为真时，一定要用到归纳假设，即要把“T(n)为真推出 T(n＋1)为真”或“T(n0)，T(n0＋1)，„，T(k-1)为真推出T(k)为真”的实质蕴含真正体现出来．否则不是数学归纳法证明．
例2 设a1，„，an为n个正数，b1，„，bn是它的一个排列．试证
证1°当n=1时，命题显然成立．
2°假设(*)式对n=k成立，则当n=k＋1时
根据数学归纳法原理，(*)式对所有大于等于1的自然数n都成立．
这里虽然形式上完成了数学归纳法的两个步骤，但第二步在证(*)式对n＋1成立的过程中，并没用到(*)对n成立的归纳假设．因此，不能说上述证法是采用了数学归纳法．事实上，在上述证明中无须用数学归纳法，用平均值不等式证明就行了．
第三，并不是凡与自然数相关的命题T(n)，都要用数学归纳法来证明；而且也不是所有这类命题都能用数学归纳法给以证明的．
这一命题是与自然数相关的命题，尽管可以对n＝0，1，2，„进行验证，但无法实现数学归纳法的第二步，因此不能用数学归纳法进行证明．
事实上，数学归纳法只适用于具有递归性的命题T(n)．
3．递归函数
一个定义在自然数集N上的函数f(n)，如果它对于每个自然数n的值可以用如下方式确定：
(1)f(0)=a(a为已知数)；
(2)存在递推关系组S，当已知/f(0)，f(1)，„，f(n-1)值以后，由S唯一地确定出f(n)的值：
f(n)=S［f(0)，f(1)，„，f(n-1)］
那么，就把这个函数f(n)，称作归纳定义的函数．简称递归函数．
在具体的递归函数例子中，关系组S可能有几个表达式，或者没有明确的解析表达式，也可能需要给出f(n)的开头若干个值．
这样定义函数是合理的，因为我们有：
定理4 当递推关系组S给定后，定义在N上的满足上述条件(1)、(2)的函数f(n)是存在而且唯一的．
证 首先指出：对任一自然数k，总可以在片断｜0，k｜上定义一个函数fk(n)，使fk(0)=a，对于片断上其他自然数 n，f(n)=S［f(0)，„，f(n-1)］．这个函数fk(n)是在｜0，k｜上唯一确定的．
现对k进行归纳证明：
1° 当k＝0时，f0(0)＝a是唯一确定的；
2°假定在｜0，k｜上已经由(1)、(2)定义了一个唯一确定的函数fk(n)，令
则fk+1(n)在片断｜0，k＋1｜上有定义，且
(1)fk+1(0)=fk(0)=a；
(2)fk+1(n)=S［fk(0)，„，fk(n－1)］
=S［fk+1(0)，„，fk+1(n－1)］，n=1，2，„，k．
因此，函数人fk+1(n)满足条件(1)、(2)．由数学归纳法知，对任何自然数k，函数fk(n)在片断｜0，k｜上唯一确定，且满足(1)、(2)．又若k1＜k2，则 fk1(n)与fk2(n)在片断｜0，k1｜上完全一致．
现作一新的函数：f(n)=fn(n)，n∈N．
首先，函数f(n)对任一n∈N都有定义，且
f(n)=fn(n)=S［fn－1(0)，„，fn-1(n－1)］
=S［f0(0)，„，fn-1(n-1)］
=S［f(0)，„，f(n-1)］
又显然f(0)＝f0(0)=a．故函数f(n)是定义在N上且满足(1)、(2)的唯一确定的函数．
例4 设函数f∶N→N，且
(1)f(0)=2，f(1)=3；
(2)f(n＋1)＝3f(n)－2f(n－1)，n≥1． 证明： f(n)＝2n＋1．
这里给出的递归函数由f(0)、f(1)两个值和一个关系式给定的关系组S确定．但有的递归函数f(0)的值隐含于关系组S之中而未直接给出．
例5(IMO－19试题)设f：N+→N＋，且
(S)
f(n＋1)＞ f(f(n))，n∈N+ 求证：对于任意n∈N＋，f(n)＝n．
证 先用数学归纳法证明命题An：任意正整数n，若m≥n，则f(m)≥ n．
显然 A1真．假设An-1真，则对任意m≥n，f(m－1)≥n-1，故f(m)＞f(f(m－1))≥2n－1，于是f(m)≥n，从而 An真．
由此可知，f(n)≥n，f(n＋1)＞f(f(n))≥f(n)．于是f单调增加．又如果有一个n使f(n)＞n，则f(n)≥n+1，f(f(n))≥f(n+1)，与已知条件(S)矛盾．故只能有 f(n)=n．
本题给出的递归函数，f(1)的值没有明显给出，但实际上隐含于关系组(S)中．
4．递归命题
一个与自然数相关的命题T(n)，一般来说，它未必是一个函数问题．现在采取如下方式来构造命题T(n)的真值函数f∶N→｛1，0｝．
如果命题T(n)的真值函数f(n)是递归函数，即
1° f(0)=1；
2° f(n＋1)= S［f(0)，„，f(n)］，且当f(0)=„=f(n)=1时，f(n＋1)=1．
那么就称T(n)是具有递归性质的命题，或简称递归命题．
实际上，所谓递归命题，就是一个与自然数相关的命题T(n)，开头(如n=0时)为真，且真值可传递并不是所有与自然数相关的命题都是递归命题．例如本节例3中的命题
是与自然数相关的命题，而且对任何n∈N，它都为真，但却不具有递归性，它的真值是不可传递的．一般而言，大多数数论问题，如哥德巴赫猜想、费马问题、孪生素数问题等，都不是递归命题．
只有递归命题才能用数学归纳法来证明．因此判别一个与自然数相关的命题T(n)是不是递归命题，是运用数学归纳法的前提．判别的关键在于，探究和发现T(n)的真值对于T(0)，„，T(n-1)真值的依赖性．而这种探究本身对于数学归纳法第二步证明，也有直接帮助．
例6(1963年北京市竞赛题)2n(n∈N＋)个球分成若干堆，从中任选两堆：甲堆p个球，乙堆q个球；若p≥q，则从甲堆取出q个加于乙堆；这作为一次挪动(变换)．证明：总可以经过有限次挪动，使所有球都归为一堆．
这是一个与自然数相关的命题，记为T(n)．当n=1时，只有两个球，或已是一堆；或两堆，每堆一个球．若后者，只须挪动一次，就变为一堆．所以T(1)为真．
T(n)真值是否有传递性呢？考察2n+1与2n，前者比后者多了一倍．如果设想每堆都是偶数个球，把每两个球用一个小袋装在一起，2n+1个球就变成了2n袋球．假设2n袋球都挪到一堆，那么2n+1个球也就挪到了一堆．这样就使T(n)的真值传递给了T(n＋1)．
现在设法先将分球的情况变为每堆球数为偶数．
假设不是每堆球数都是偶数，则球数为奇数的堆数一定为偶数(为什么？)．现将这2r堆奇数个球的堆两两配对，每对从较多的一堆向较少的一堆挪动一次．那么这2r堆每堆球数均为偶数(也可能出现空堆，如果一对中两堆球数相等的话)．这样便可以实施数学归纳法的第二步证明了．
向量范数的等价性定理设 ||x||s，||x||t为Rn上向量，的任意两种范数，则存在常数 c1，c2 > 0,使得对一切x∈Rn，有c1||x||s ≤ ||x||t ≤ c2||x||s证明：只需证明不等式在||x||s = ||x||......
等价与蕴含证明的一般方法 A B A B 真值表技术 命题演算 (等价变换) · 列出 A、B 的真值表 · 列出 A B 的真值表 · A B · A B T 分两步: 1.证 A B 具体......
1、爬升限制的起飞重量的影响因素有：气压高度、襟翼位置、机场气温2、下列有关爬升限制的起飞重量的影响正确的是襟翼越小，爬升限制的起飞重量越大3、增大V1速度的因素有：机场......
《小数的性质》教学设计努日木镇中心校：沈 春一、教学内容人教版小学数学第八册第58页、59页的例1、例2、例3、，练习十第1-----3题。二、教学目标1、使学生初步理解小数的性......
龙源期刊网 http://.cn基于补码等价定义的Booth算法证明作者：王顺利来源：《现代电子技术》2012年第12期摘要：Booth算法是定点补码乘法的基本运算方法。一般文献中，Booth算法都是......
