第1讲 数学归纳法

第一讲 数学归纳法

1. 教学基本要求

了解数学归纳法的实质，理解不同形式数学归纳法之间的关系，能够选用数学归纳法的恰当形式解决相关问题． 2. 教学具体内容

最小数原理，跳跃归纳法，倒退归纳法等．

重点与难点：归纳起点的选择，归纳形式的选择，归纳变量的选择． 教学内容

数学归纳法是证明序列命题的常用方法．设n是整数，P(n)是与n有关的命题，A是非负整数集的一个子集，要证明?n?A，命题P(n)成立，这时可以考虑用数学归纳法．数学归纳法有多种表现形式，中学数学中常用的第一数学归纳法与第二数学归纳法是它的两种重要表现形式．在竞赛数学中，还需要了解其他的表现形式． 一、基本原理

数学归纳法发源于自然数的归纳公理或最小数原理．可以证明自然数的归纳公理或最小数原理等价，所以人们常用最小数原理证明数学归纳法．

?M，有a'?M，则M?N．皮亚诺（归纳）公理：若M?N，且1?1?M；2??a

即自然数的某个集合若含1，且如果含一个自然数a就一定含a’，那么这个集合含全体自然数）

最小数原理：设M是自然数集的一个非空子集，则M中必有最小数，即?n0?M，使得?n?M，均有n?n0.

定理1 设A是一个非空集合，A1,A2,,Ak,均为非空集合，

A?A1A2Ak

若?n?A1，有命题P(n)成立，又在假设?n?Ak，命题P(n)成立的前提下，能推出

?n?Ak?1，命题P(n)成立，则?n?A，命题P(n)成立．

在定理1中，当取Ak??k?,k?Z?，则得到第一数学归纳法． 在定理1中，当取Ak??1,2,3,k?,k?Z?，则得到第二数学归纳法．

在定理1中，设l?N,l?2，令

A1??1,2,3,，l?,A2??l?1,l?2,l+3,，2l?,

Ak??(k?1)l?1,(k?1)l?2,(k?1)l+3,，kl?,则得到跳跃式归纳法． 数学归纳法的几种形式

定理2（第一数学归纳法）设P(n)是关于自然数n的命题，若 Ⅰ（奠基）P(n)在n?1时成立

Ⅱ（归纳）P(k)（k是任意自然数）成立的假设下可以推出P(k?1)成立． 则P(n)对一切自然数n都成立．

这是数学归纳法的标准形式

证明：设M是使命题成立的所有自然数组成的集合，则由 Ⅰ 1?M； Ⅱ 若k?M，则k??M，由归纳公理，得证．

第一数学归纳法的一种变形（移动起点）设P(n)是关于自然数n的命题，若 ⅠP(n)在n?n0时成立．其中n0为任何一个具体的自然数． ⅡP(k)（k?n0）成立的假设下可以推出P(k?1)成立． 则P(n)对一切自然数n（n?n0）都成立．

定理3第二数学归纳法（串值归纳法）设P(n)是关于自然数n的命题，若 ⅠP(n)在n?1时成立．

ⅡP(m)对于所有适合m?k的自然数m成立的假设下可推出P(k)成立． 则P(n)对一切自然数n都成立．

第二数学归纳法的一种变形（增多起点）设P(n)是关于自然数n的命题，若ⅠP(n)在n?1，n?2时成立．

页

2

Ⅱ 假设P(k),P(k?1)真，则P(k?2)真． 则P(n)对一切自然数n都成立．

定理4 跳跃式归纳法（加大跨度）设P(n)是关于自然数n的命题，若 ⅠP(1),P(2),?,P(l)（l?2）为真命题．

Ⅱ在P(k)（k是任意自然数）成立的假设下可以推出P(k?l)成立． 则P(n)对一切自然数n都成立．

在跳跃式归纳法中，人们常把整数l称为归纳跨度或归纳步长．

定理5（反向归纳法）设P(n)是关于自然数n的命题，若 Ⅰ 有无限多个值使P(n)成立．

Ⅱ 在P(k)（k是任意自然数）成立的假设下可以推出P(k?1)成立． 则P(n)对一切自然数n都成立． 二、试题生成

编制数学归纳法试题的方法之一是改变归纳的跨度，对于与整数n有关的命题

P(n)，如果由P(k)成立不易推出P(k?1)成立，但由P(k)成立容易推出P(k?l)(l?2)成

立，则可用P(n)的这一特性编制与跳跃归纳法相关的试题．

例1 已知n为正整数(n?45)，求证：必存在非负整数x,y，使得n?4x?9y． 证明： 45?5?9

46?5?9?1?4?7?9?247?5?9?2?4?5?9?3 48?5?9?3?4?3?9?4假设n?k时命题成立，即存在非负整数x,y，使得k?4x?9y． 则k?4?4x?9y?4?4(x?1)?9y．

所以对n为正整数(n?45)，必存在非负整数x,y，使得n?4x?9y．

编制数学归纳法相关试题的另一种方法是将一般问题特殊化，若命题P(n)对一切

3

页

正整数都成立，那么对于特定的正整数n0，命题P(n0)也成立． 例2 证明方程x2?y2?z2011 存正整数解． 分析：证明方程x2?y2?zn(n?Z?) 存正整数解．

证明：当n=1时，命题成立，即x2?y2?z有正整数解（1，2，5）

当n=2时，命题成立，即x2?y2?z2有正整数解（3，4，5）

假设n?k时命题成立，即x2?y2?zk存在正整数解(x0,y0,z0)，即x02?y02?z0k 记x1?x0?z0，y1?y0?z0，所以x1,y1?Z?，

且x12?y12?x02?z02?y02?z02?(x02?y02)?z02?z0k?z02?z0k?2 上式说明(x1,y1,z0)是方程x2?y2?zk?2的一组正整数解． 说明步长为2时，命题成立． 由跳跃归纳法得原命题成立． 显然n?2011时，命题成立，即方程x2?y2?z2011 存正整数解． 三、方法解读

在数学归纳法的教学中应注意

（1）要使学生弄清数学归纳法与普通形式逻辑中的归纳法的区别．

归纳法是通过观察、试验、推理或猜测，得出一个关于全体对象的判断，属于归纳．分为完全归纳法和不完全归纳法．完全归纳法是考察一类事物的每一对象肯定它们都具有某一属性，从而得出这类事物都有这一属性的一般性结论．不完全归纳法是考察一类事物的部分对象具有某一属性，从而得出这类事物都有这一属性的一般性结论．

数学归纳法是对给定结论予以证明，属于证明． （2）帮助学生正确理解数学归纳法． ① 数学归纳法中的两个步骤，缺一不可． 例如不要Ⅰ（奠基）． 例 证明所有正整数都相等．

证：假设n?k时，第k个整数等于第k?1个整数，即k?k?1；

两边都加上1，得到k?1?k?2，即第k?1个整数等于第k?2个整数 所以，n?k?1时命题也成立．

4

页