DOC《1.5 归纳法原理与反归纳法》

如果由假定命题T对自然数k正确,就能推出命题T对自然数正确.则命题对一切自然数都正确. 证明 因为任意自然数 由于命题对一切中的r都正确,所以命题对都正确,因而对一切n命题都正确. 下面我们给出一个应用跳跃归纳法的一个例子. 例4 求证用面值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分邮票构成,再加上一个3分邮票,就使分邮资可用3分与5分邮票构成.由跳跃归纳法知命题对一切n≥8都成立. 下面我们介绍双归纳法,所谓双归纳法是所设命题涉及两个独立的自然数对(m,n),而不是一个单独的自然数n. 双归纳法 若命题T与两个独立的自然数对m与n有关, (1)若命题T对m=1与n=1是正确的;

(2)若从命题T对自然数对(m,n)正确就能推出该命题对自然数对(m+1,n)正确,和对自然数对(m,n+1)也正确. 则命题T对一切自然数对(m,n)都正确. 关于双归纳法的合理性证明我们不予说明,只给出一个例子. 例5 求证对任意自然数m与n均有 证明 (1)当时,命题显然正确,即(2)设命题对自然数对m与n正确,即 这时 即命题对数对(m+1,n)正确;

另一方面 即命题对数对(m,n+1)也正确,由双归纳法知,命题对一切自然数对(m,n)都成立. 反归纳法 若一个与自然数有关的命题T,如果 (1)命题T对无穷多个自然数成立;

(2)假设命题T对n=k正确,就能推出命题T对n=k-1正确.则命题T对一切自然数都成立;

上述归纳法称为反归纳法,它的合理性我们做如下简短说明: 设M是使命题T不正确的自然数,如果M是非空集合,则M中存在最小数m,使得命题T对k=m不正确;

由于命题对无穷多个自然数正确,所以存在一个,且命题T对正确;

由于命题T对m不正确,所以命题对也不正确,否则由命题T对正确就推出命题T对m正确.矛盾!这样,命题T对m+2也不正确,经过次递推后,可得命题T对也不正确.这与已知矛盾,所以M是空集合. 反归纳法又称倒推归纳法,法国数学家柯西(1789-1857)首次用它证明了n个数的算术平均值大于等于这n个数的几何平均值. 例6 求证n个正实数的算术平均值大于或等于这n个数的几何平均值,即 证明 当n=2时, 因此命题对n=2正确. 当n=4时, 因此命题对n=4正确 同理可推出命题对n=23=8,n=24,…,n=2s…都正确(s为任意自然数),所以命题对无穷多个自然数成立. 设命题对n=k正确,令则(容易证明上述是一个恒等式.) 由归纳假设命题对n=k正确,所以 所以 即 命题对n =k-1也正确,由反归纳法原理知,命题对一切自然数成立. 由于上述不等式是著名不等式,我们再给出几种证明: 前已证明,命题对n=2m时正确,设n........