1、数学归纳原理和最小数原理的等价性证明这两个原理都是自然数公理系统中最基本的原理，人们常常用最小数原理证明数学归纳原理。我发现用数学归纳原理也可以证最小数原理。所谓的最小数原理是指：自然数集合的任意非空子集必有最小元素。一：用数学归纳原理证最小数原理。 当自然数的非空子集只含一个元素时，这个元素就是最小元素。设n 元集有最小元素，对于 n+1元集，新加入的元素与 n 元集中的最小数比较，若新加入的元素不大于该最小数，则新加入的元素为最小数，否则，原来的 n 元集中的最小数仍是 n+1 元集的最小数。由数学归纳原理，含任意个自然数数目的自然数子集都有最小数。得证。二：用最小数原理证数学归纳原理：p
2、(o)成立，且 p(n)成立可导出 p(n+1)成立，则对于一切自然数 n,p(n)成立。否则，若对于若干个（可能有限个，也可能无限个）自然数 m1,mi(i1）使命题不成立，由最小数原理，这若干个自然数有最小数记为 w，而且，w 一定是正数，那么，就一定存在唯一的自然数b,b+1=w.b 不属于这个使命题不成立的元素组成的集合，因为 b 比最小数还小。则 p(b)是成立的，由规则，p(b+1)也成立即 p(w)成立。矛盾。故对于一切自然数 n,p(n)成立。证毕。其实以上发现也没啥大不了的，很直观浅显。这两个原理的等价性得证后，两者中的任意一条都可以作为皮亚杰五条公理中的一条吗？不行！因为最
3、小数原理中的小于最开始还是没有定义的！。还有，该等价关系非我第一次发现，由于其十分简单，在我发现等价性后，我在华罗庚的数学归纳法最后找到了同样的结论。归纳原理和数学归纳法1数学归纳法的理论依据归纳法和演绎法都是重要的数学方法归纳法中的完全归纳法和演绎法都是逻辑方法；不完全归纳法是非逻辑方法，只适用于数学发现思维，不适用数学严格证明数学归纳法既不是归纳法，也不是演绎法，是一种递归推理，其理论依据是下列佩亚诺公理中的归纳公理：存在一个自然数 0N；每个自然数 a 有一个后继元素 a，如果 a是 a 的后继元素，则 a 叫做 a的生成元素；自然数 0 无生成元素；如果 a=b，则 a=b；(归纳公理
4、)自然数集 N 的每个子集合 M，如果 M 含有 0，并且含有 M 内每个元素的后继元素，则 MN自然数就是满足上述佩亚诺公理的集合 N 中的元素关于自然数的所有性质都是这些公理的直接推论由佩亚诺公理可知，0 是自然数关于“后继”的起始元素，如果记01，1=2，2=3，n=n1，则N=0，1，2，n，由佩亚诺公理所定义的自然数与前面由集合所定义的自然数，在本质上是一致的90 年代以前的中学数学教材中，将自然数的起始元素视作 1，则自然数集即为正整数集现在已统一采取上面的记法，将 0 作为第一个自然数定理 1(最小数原理)自然数集 N 的任一非空子集 A 都有最小数这本是自然数集 N 关于序关系
5、()为良序集的定义现在用归纳公理来证明证 设 M 是不大于 A 中任何数的所有自然数的集合，即M=nnN 且 nm，对任意 mA由于 A 非空，至少有一自然数 aA，而 a1(a)不在 M 中所然，就有 1 0M(0 不大于任一自然数)；2 若 mM，则 m1M根据归纳公理，应有 MN此与 MN 相矛盾这个自然数 m0就是集合 A 的最小数因为对任何 aA，都有 m0意 aA，于是 m01M，这又与 m0的选取相矛盾反之，利用最小数原理也可以证明归纳公理因此，最小数原理与归纳公理是等价的定理 2(数学归纳法原理)一个与自然数相关的命题 T(n)，如果1 T(n 0)(n00)为真；2 假设 T
6、(n)(nn0)为真，则可以推出 T(n1)也为真那么，对所有大于等于 n0的自然数 n，命题 T(n)为真证 用反证法若命题 T(n)不是对所有自然数 n 为真，则M=mmN，mn 0且 T(m)不真非空根据定理 1，M 中有最小数 m0由 1， m 0n 0，从而 m01n 0且 T(m0-1)为真由 2，取 n=m0-1 即知 T(m0)为真此与 T(m0)不真相矛盾从而证明了定理 2在具体运用数学归纳法进行数学证明时，有多种不同形式运用定理 2 中两个步骤进行证明的，为型数学归纳法经常使用的还有型数学归纳法，型数学归纳法是：如果命题 T(n)满足1 对某一自然数 n00，T(n 0)为
7、真；2 假设对 n0kn 的 k， T(k)为真，则可以推出 T(n1)也真那么对所有大于等于 n0的自然数，命题 T(n)都真定理 3 型数学归纳法和型数学归纳法等价证 假设命题 T(n)对 n=n0为真，于是只须证明“由 T(n)(nn 0)为真，可以推出 T(n1)也为真”的充要条件为“由 T(k)(n0kn)为真，可以推出 T(n+1)也为真”1 充分性若“由 T(n)(nn 0)为真，可以推出 T(n1)也为真”，则对n0kn，T(k)为真，特别 T(n)为真，因此 T(n1)也为真2 必要性用反证法若“由 T(k)(n 0kn)为真，可以推出 T(n1)也为真”，但并非对所有大于等
8、于 n0的自然数 n，由 T(n)为真，可以推出 T(n1)也为真，则 M=mmN， mn 0且由 T(n)为真推不出 T(n1)也为真非空由定理 1，M 中有最小数 m0，且对 n0km 0的 k，由 T(k)为真，可以推出 T(k1)也为真特别由 T(n 0)为真可知 T(n 0+1)为真，由T(n01)为真可知 T(n 02)为真，由 T(m01)为真可知 T(m 0)为真现已知 T(n0)为真，所以 T(n0)， T(n 0+1)， T(m 0)都为真，由此可知 T(m 01)也为真，所以由 T(m 0)为真推出了 T(m01)也为真这与m0的选取矛盾由定理 3 可知，型数学归纳法也是
9、合理的推理方法2数学归纳法在应用中要注意的问题第一，证明的两个步骤缺一不可第一步是归纳的基础，第二步是归纳的传递尤其是不可忽视第一步的验证例 1 试证135(2n1)(n1) 21证 假设当 n=k 时公式成立，则135(2n-1)(2n+1)135(2n-1)(2n1)n 212n1(n1) 21完成了数学归纳法的第二步，但结论显然是错误的为什么？因为缺少第一步事实上，当 n=0 时，公式不成立如果缺了第二步，则不论对多少个自然数来验证命题 T(n)的正确性，都不能肯定命题对所有自然数都正确例如，哥德巴赫猜想“任何不小于 6 的偶数都可以表成两个奇素数之和”，虽然对大量偶数进行了具体验证，但
10、因缺少第二步归纳传递，所以仍只停留在归纳的第一步上它至今仍只是个猜想而已第二，第二步在证明 T(n1)为真时，一定要用到归纳假设，即要把“T(n)为真推出 T(n1)为真”或“T(n 0)， T(n 01)，T(k-1)为真推出 T(k)为真”的实质蕴含真正体现出来否则不是数学归纳法证明例 2 设 a1，a n为 n 个正数，b 1，b n是它的一个排列试证证 1当 n=1 时，命题显然成立2假设(*)式对 n=k 成立，则当 n=k1 时根据数学归纳法原理，(*)式对所有大于等于 1 的自然数 n 都成立这里虽然形式上完成了数学归纳法的两个步骤，但第二步在证(*)式对 n1 成立的过程中，并
11、没用到(*)对 n 成立的归纳假设因此，不能说上述证法是采用了数学归纳法事实上，在上述证明中无须用数学归纳法，用平均值不等式证明就行了第三，并不是凡与自然数相关的命题 T(n)，都要用数学归纳法来证明；而且也不是所有这类命题都能用数学归纳法给以证明的这一命题是与自然数相关的命题，尽管可以对 n0，1，2，进行验证，但无法实现数学归纳法的第二步，因此不能用数学归纳法进行证明事实上，数学归纳法只适用于具有递归性的命题 T(n)3递归函数一个定义在自然数集 N 上的函数 f(n)，如果它对于每个自然数 n 的值可以用如下方式确定：(1)f(0)=a(a 为已知数)；(2)存在递推关系组 S，当已知/
12、f(0)，f(1)，f(n-1)值以后，由 S 唯一地确定出 f(n)的值：f(n)=Sf(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)=Sf(0)，f(n-1
13、)这个函数 fk(n)是在0，k上唯一确定的现对 k 进行归纳证明：1 当 k0 时，f 0(0)a 是唯一确定的；2假定在0，k上已经由(1)、(2)定义了一个唯一确定的函数fk(n)，令则 fk+1(n)在片断0，k1上有定义，且(1)f k+1 (0)=fk(0)=a；(2)f k+1(n)=Sf k(0)，f k(n1)=Sf k+1(0)，f k+1(n1)，n=1，2，k因此，函数人 fk+1(n)满足条件(1)、(2)由数学归纳法知，对任何自然数 k，函数 fk(n)在片断0，k上唯一确定，且满足(1)、(2)又若 k1k 2，则 f k1(n)与 fk2(n)在片断0，k 1上
14、完全一致现作一新的函数：f(n)=f n(n)， nN首先，函数 f(n)对任一 nN 都有定义，且f(n)=f n(n)=Sf n1 (0)，f n-1(n1)=Sf 0(0)，f n-1(n-1)=Sf(0)，f(n-1)又显然 f(0)f 0(0)=a故函数 f(n)是定义在 N 上且满足(1)、(2)的唯一确定的函数例 4 设函数 fNN，且(1) f(0)=2，f(1)=3；(2) f(n1)3f(n)2f(n1)，n1证明： f( n)2 n1这里给出的递归函数由 f(0)、f(1)两个值和一个关系式给定的关系组 S 确定但有的递归函数 f(0)的值隐含于关系组 S 之中而未直接给
15、出例 5(IMO19 试题)设 f：N +N ，且(S) f(n1) f(f(n)， nN +求证：对于任意 nN ，f(n)n证 先用数学归纳法证明命题 An：任意正整数 n，若 mn，则 f(m) n显然 A 1真假设 An-1真，则对任意 mn，f(m 1)n-1，故 f(m)f(f(m1)2n1，于是 f(m)n，从而 An 真由此可知，f(n)n，f(n1)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
16、)中4递归命题一个与自然数相关的命题 T(n)，一般来说，它未必是一个函数问题现在采取如下方式来构造命题 T(n)的真值函数 fN1，0如果命题 T(n)的真值函数 f(n)是递归函数，即1 f(0)=1；2 f(n1)= Sf(0)，f(n)，且当 f(0)=f(n)=1 时， f( n1)=1那么就称 T(n)是具有递归性质的命题，或简称递归命题实际上，所谓递归命题，就是一个与自然数相关的命题 T(n)，开头(如 n=0 时)为真，且真值可传递并不是所有与自然数相关的命题都是递归命题例如本节例 3 中的命题是与自然数相关的命题，而且对任何 nN，它都为真，但却不具有递归性，它的真值是不可传
17、递的一般而言，大多数数论问题，如哥德巴赫猜想、费马问题、孪生素数问题等，都不是递归命题只有递归命题才能用数学归纳法来证明因此判别一个与自然数相关的命题 T(n)是不是递归命题，是运用数学归纳法的前提判别的关键在于，探究和发现 T(n)的真值对于 T(0)，T(n-1)真值的依赖性而这种探究本身对于数学归纳法第二步证明，也有直接帮助例 6(1963 年北京市竞赛题)2 n(nN )个球分成若干堆，从中任选两堆：甲堆 p 个球，乙堆 q 个球；若 pq，则从甲堆取出 q 个加于乙堆；这作为一次挪动(变换)证明：总可以经过有限次挪动，使所有球都归为一堆这是一个与自然数相关的命题，记为 T(n)当 n
18、=1 时，只有两个球，或已是一堆；或两堆，每堆一个球若后者，只须挪动一次，就变为一堆所以 T(1)为真T(n)真值是否有传递性呢？考察 2n+1与 2n，前者比后者多了一倍如果设想每堆都是偶数个球，把每两个球用一个小袋装在一起，2 n+1个球就变成了 2n袋球假设 2n袋球都挪到一堆，那么 2n+1个球也就挪到了一堆这样就使 T(n)的真值传递给了 T(n1)现在设法先将分球的情况变为每堆球数为偶数假设不是每堆球数都是偶数，则球数为奇数的堆数一定为偶数(为什么？)现将这 2r 堆奇数个球的堆两两配对，每对从较多的一堆向较少的一堆挪动一次那么这 2r 堆每堆球数均为偶数(也可能出现空堆，如果一对中两堆球数相等的话)这样便可以实施数学归纳法的第二步证明了
