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

1.

5 归纳法原理与反归纳法 数学归纳法是中学教学中经常使用的方法.中学教材中的数学归纳法是这样叙述的:如果一个命题与自然数有关,命题对n=1正确;

若假设此命题对n-1正确,就能推出命题对n也正确,则命题对所有自然数都正确.通俗的说法:命题对n=1正确,因而命题对n=2也正确,然后命题对n=3也正确,如此类推,命题对所有自然数都正确.对于中学生来说,这样形象地说明就足够了;

但是毕竟自然数是无限的,因而上述描述是不够严格的,有了皮阿罗公理后,我们就能给出归纳法的严格证明. 定理1.19 如果某个命题T,它的叙述含有自然数,如果命题T对n=1是正确的,而且假定如果命题T对n的正确性就能推出命题T对n+1也正确,则命题T对一切自然数都成立.(第一数学归纳法) 证明 设M是使所讨论的例题T正确的自然数集合,则(1) . 设,则命题T对n正确,这时命题对也正确,即(2) 所以由归纳公理D,M含有所有自然数,即命题T对所有自然数都成立. 下面我们给出一个应用数学归纳法的命题. 例1 求证 证明 (1)当n=1时,有 所以n=1,公式正确. (2)假设当k=n时,公式正确,即 那么当k=n+1时,有 所以公式对n+1也正确. 在利用数学归纳法证明某些命题时,证明的过程往往归纳到n-1或n-2,而不仅仅是n-1,这时上述归纳法将失败,因而就有了第二数学归纳法.在叙述第二归纳法以前,我们先证明几个与自然数有关的命题. 命题1 若,则. 证明 因为 所以 所以 命题2 1是自然数中最小的一个. 证明 若,则有前元b,所以 命题3 若,则. (即数与+1是邻接的两个数,中间没有其他自然数,不存在b,使得.) 证明 若,则. 因为,所以,即. 由上述有关自然数大小的命题,我们得出下面定理,有时也称为最小数原理. 定理1.20 自然数的任何非空集合A含有一个最小数,即存在一个数,使得对集合A中任意数b,均有. 证明 设M是这样的集合: 对于M中任意元素,对A中任意元素,均有 则M是非空集合. 因为,由归纳公理(4)知,一定存在一个元素. 但,即, 否则由得M=N,这显然不可能. 现在我们证明 .因为若 , 则A中任意元素 所以,与矛盾,所以m即为A中最小元素. 上述定理也称为最小数原则,有的作者把它当成公理,用它也可以证明数学归纳法,下面我们给出所谓第二数学归纳法.(第二数学归纳法) 定理1.21 对于一个与自然数有关的命题T,若(1)当n=1时命题T正确;

(2)假设命题T对正确,就能推出命题T对正确. 则命题T对一切自然数正确. 证明 如果命题T不是对所有自然数都成立,那么使命题不成立的自然数集合M就是非空集合,由定理1.20,M中含有一个最小数k,且(∵k=1命题正确),所以对一切,命题T成立,又由(2)推出命题T对k正确.结论矛盾. 下面我们给出两个只能应用第二数学归纳法而不能应用第一归纳法解题的例子. 例2 已知数列,有且求证. 证明 对n=1,有 所以命题对n=1正确. 假设命题对正确,则 所以命题对n=k正确. 由第二数学归纳法本题得证. 例3 已知任意自然数均有 (这里) 求证 证明 (1)当n=1时,由,得 所以命题对n=1正确. (2)假设对命题正确,这时 , 当n=k+1时, (1) 但是 (2) 又因为归纳假设对命题正确,所以 所以 由(1)和(2)式得 消去,得 解得 舍去) 所以命题对n=k+1也正确. 上边的两个例子,实际上例2命题归结到n-1和n-2,而例3则需要归结到1,2,…k,由此可见,第二数学归纳法的作用是不能由第一归纳法所替代的. 现在我们继续讲数学归纳法.当然,归纳并一定从n=1开始,例如例2数列的例子,也可以从某数k开始.数学归纳法还有许多变形,其中著名的有跳跃归纳法、双归纳法、反归纳法以及跷跷板归纳法等,下面我们就逐个介绍这些归纳法. 跳跃归纳法 若一个命题T对自然数,都是正确的;