数学归纳法的一种推广形式

吴捷云

摘要： 数学归纳法是证明与正整数有关的命题的一种重要方法.本文在反向数学归纳法和螺旋式数学归纳法的基础上对数学归纳法做进一步的推广，并给出了相关的应用.

关键词： 正整数数学归纳法反向螺旋式

数学归纳法的基本形式是：

引理1[1]：设有一个与正整数有关的命题.如果

（1）当n=1时，命题成立；

（2）假设n=k时命题成立，则n=k+1时命题也成立，

那么这个命题对于一切正整数n都成立.

对有些命题可以考虑用反向数学归纳法（引理2）或螺旋式数学归纳法（引理3）来证明.

引理2[2]：设有一个与正整数n有关的命题.如果

（1）命题对无穷个正整数n成立；

（2）假设n=k时命题成立，则n=k—1时命题也成立，

那么这个命题对于一切正整数n都成立.

引理3[3]：设P（n）和Q（n）是与正整数n有关的命题，若

（1）P（1）成立；

（2）对于任意正整数k，假设P（k）成立，则Q（k）成立；假设Q（k）成立，则P（k+1）成立.

那么命题P（n）和Q（n）对于一切正整数n都成立.

现在把反向数学归纳法与螺旋式数学归纳法结合起来就得到数学归纳法的一种新的推广形式.

定理：设P（n）和Q（n）是与正整数n有关的命题，若

（1）P（n）和Q（n）都对无穷多个正整数n成立；

（2）存在正整数c，对于任意正整数k≥c，假设P（k）成立，则Q（k）成立；对于任意正整数k≥c+1，假设Q（k）成立，则P（k—1）成立.

那么命题P（n）和Q（n）对于一切正整数n≥c都成立.

证明：设使命题P（n）不成立的正整数n≥c所成的集合为A.假设A不是空集，根据最小数原理，A中必存在最小数a，于是命题P（a）不成立.因为P（n）对无穷多个正整数n成立，所以总可以找到一个正整数b>a，使得P（b）成立.这样的话，P（b）成立？圯Q（b）成立？圯P（b—1）成立？圯Q（b—1）成立？圯P（b—2）成立……经过有限步后，可推得P（a）也成立，这就导致矛盾，故A是空集.所以命题P（n）对所有的正整数n≥c都成立.

根据（2），对于任意正整数k≥c，当P（k）成立时Q（k）必成立.因此由命题P（n）对所有的正整数n≥c都成立可知命题Q（n）也对所有的正整数n≥c都成立.

综上，命题P（n）和Q（n）对于一切正整数n≥c都成立.证毕.

例：求证：用3分、5分或者4分、5分可以支付任何n（n≥12）分的邮资.

证明：记用3分、5分可以支付任何n（n≥12）分的邮资为命题P（n），用4分、5分可以支付任何n（n≥12）分的邮资为命题Q（n）.

（1）当n是3或者5的倍数时，3分、5分可以支付n分的邮资；同理，当n是4或者5的倍数时，4分、5分可以支付n分的邮资.因此命题P（n）和Q（n）都对无穷多个正整数n成立.

（2）首先，对于任意正整数n（n≥12），假设命题P（n）成立，那么n分的邮资可以用3分、5分支付，设3分的张数分别为x，5分的张数分别为y.分两种情况讨论4分、5分能否支付n分邮资：

①如果x=0，则只用5分可以支付n分邮资.

②如果x≥1，因为用3分、5分可以支付时，原来每5张3分都可以换成3张5分支付，则只需讨论x=1，2，3，4的情况.

当x=1时，有y≥3.这时只需将这张3分和1张5分换成2张4分即可；

当x=2时，有y≥2.将这2张3分和2张5分换成4张4分即可；

当x=3时，有y≥1.将这3张3分和1张5分换成1张4分和2张5分即可；

当x=4，将这4张3分换成3张4分即可.

从以上4种情况知4分、5分可以支付n分邮资.即Q（n）成立.

其次，对于任意正整数n（n≥13），假设n分的邮资可以用4分、5分支付，张数分别为x，y，分两种情况讨论3分、5分能否支付（n—1）分邮资：

①如果x=0，则y≥3，那么只需将2张5分换成3张3分，即3分、5分可以支付（n—1）分邮资.

②如果x≥1，因为用3分、5分可以支付时，原来每5张4分都可以换成4张5分支付，则只需讨论x=1，2，3，4的情况.

当x=1时，只需将这张4分换成3分即可；

当x=2时，有y≥1.将这2张4分和1张5分换成4张3分即可；

当x=3时，将这3张4分换成2张3分和1张5分即可；

当x=4时，将这4张4分换成5张3分（或者3张5分）即可.

从以上4种情况知3分、5分可以支付（n—1）分邮资.即P（n—1）成立.

根据定理，命题P（n）和Q（n）对于一切正整数n≥12都成立，即用3分、5分或者4分、5分可以支付任何n（n≥12）分的邮资.证毕.

参考文献：

[1]张禾瑞，郝鈵新.高等代数[M]（第五版）.北京：高等教育出版社，2007：15—17.

[2]郑学群.反向数学归纳法[J].中学数学，1995，（6）：44—46.

[3]方延伟.数学归纳法[M].武汉：湖北教育出版社，2002：156—178.

[4]孙宗明.试论数学归纳法[J].开封大学学报，1997，（3）：6—12.