数学归纳法的七种变式及其应用

x1?x2?????xm?n为x1?n

n 显然，此方程只有一组解，而由Cn?m?1式可知，方程x1?n的非负整数解的组数为nCn?1，因此p?n,1?对任意正整数n成立.

（3） 假设结论对p?n?1,m?和p?n,m?1?成立,即假设不定方程

x1?x2?????xm?n?1

n?1的非负整数解的组数为Cn?m，不定方程

x1?x2?????xm?xm?1?n

n的非负整数解的组数为Cn?m.

现在来考虑不定方程

x1?x2?????xm?xm?1?n?1

的非负整数解的组数，该方程的非负整数解可分为两类： 第一类 当xm?1?0时，方程

x1?x2?????xm?xm?1?n?1

变为

x1?x2?????xm?n?1，

所以方程

x1?x2?????xm?xm?1?n?1

n?1满足xm?1?0的非负整数解的组数为Cn?m.

第二类 当xm?1?0时，令xm?1?xm?1?1?xm?1?0?，则方程

x1?x2?????xm?xm?1?n?1

变为

x1?x2?????xm?xm?1?n.

方程

x1?x2?????xm?xm?1?n?1

与方程

5

x1?x2?????xm?xm?1?n

实为同一方程，所以，方程x1?x2?????xm?xm?1?n?1满足xm?1?0的非负整数解的组数

n?1为Cn?m.

因此,方程

x1?x2?????xm?xm?1?n?1

的非负整数解的组数为

n?1nn?1n?1 Cn?m?Cn?m?Cn?m?1?C?n?1???m+1??1这表明，命题p?n?1,m?1?成立.于是，由二重归纳法知，对任意正整数n和m，命题都成立.

2.5 螺旋式归纳法??

1现有两个与自然数n有关的命题A?n?，B?n?.如果满足

?1?A?1?是正确的.

?2?假设A?k?成立，能导出B?k?成立，假设B?k?成立，能导出A?k?1?成立.

这样就能断定对于任意的自然数n，A?n?和B?n?都正确.

例5 数列?an?满足a2l?3l2，a2l?1?3l?l?1??1其中l是自然数，又令Sn表示数列?an?的前n项之和，求证：

1 S2l?1?l?4l2?3l?1? （1）

21S2l?l?4l2?3l?1? （2）

2证明：这里可把等式（1）：

1S2l?1?l?4l2?3l?1?

2看作命题A?l?，把等式（2）：

1S2l?l?4l2?3l?1?

2 看作命题B?l?(l为自然数). ① l?1时，S1?1，等式（1）成立. ② 假设l?k时，等式（1）成立.即

6

S2k?1?1k?4k2?3k?1? 2那么

S2k?S2k?1?a2k?11k?4k2?3k?1??3k2=k?4k2?3k?1?. 22即等式（2）也成立.这就是说，若A?k?成立可导出B?k?成立.

又假设B?k?成立，即

S2k?1k?4k2?3k?1?. 2那么

S2k?1?S2k?ak?1?1k?4k2?3k?1????3?k?1?k?1?? 2132224k?12k?12k?4?3k?6k?3???k?1??=?????? 2132=?4?k?1??3?k?1???k?1??

?2?12=?k?1??4?k?1??3?k?1??1?.

??2这就是说，若命题B?k?成立，可以导出命题A?k?1?也成立.由①、②可知，对于任意的自然数l等式（1）、（2）都成立.

显然，这种螺旋式归纳法也实用于多个命题的情形，在原有的基础上再加入C?n?也是成立的. 2.6 跳跃归纳法??

1若一个命题Ｔ对自然数1,2,???,l,都是正确的；如果由假定命题T对自然数k正确，就能推出命题T对自然数k?l正确．则命题对一切自然数都正确．

证明： 因为任意自然数

n?lq?r0?r?l

由于命题对一切0?r?l中的r都正确，所以命题对l,r?l,r?2l???r?kl???都正确，因而对一切n命题都正确．

例6 求证用面值3分和5分的邮票可支付任何n(n?8)分邮资．

证明： 显然当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分

7

邮票构成，再加上一个3分邮票，就使n?3分邮资可用3分与5分邮票构成．由跳跃归纳法知命题对一切n?8都成立． 2.7 关于实数的连续归纳法??

3设p?x?是关于实数x的一个命题，如果： ⑴ 有a，当x?a时，p?x?成立；

⑵如果对所有小于y的x，p?x?成立，则由z?y，使得对所有小于z的x，p?x?成立；

则对所有实数x，p?x?成立.

例7 证明连续函数的介值定理：设f?x?是?a,b?上的连续函数，f?a??0?f?b?， 则有c??a,b?，使得f?c??0.

证明： 不妨令f?x?在(??,a]上恒为f?a?，在[b,??)上恒为f?b?.用反证法，设没

有实数c，使得f?c??0.考虑命题p?x?：f?x??0.则有：

⑴显然，当x?a时p?x?成立；

⑵如果对所有小于y的x，p?x?成立，即f?x??0；由连续性可得f?y??0.由反证法假设，f?y?不能为0，故f?y??0.再由连续性，有d?0，使得f?0在?y?d,y?d?上成立.故有z?y?d?y，对所有小于z的x，p?x?成立.

由连续归纳法，对所有实数x，p?x?成立：f?x??0.这与f?b??0矛盾，说明反证法假设不成立.

下面，我们用连续归纳法证明柯西收敛准则.

5例8??（Cauchy 收敛准则）数列?an?收敛????0，存在一个正整数N，?n?N，

?m?N，an?am??.

证明??：必要性易证.现证充分性.

6?a? 若?an?有无穷多项相等，不妨设an1?an2?????ank?????a，则?an?收敛于a.

事实上，由条件???0，存在一个正整数N，?n0?N,使得an0=a，?n?N，

8