2(2)数学归纳法.ppt

第二次课 数学归纳法 数学归纳法 数学归纳法的现实模型 数数 从袋子里摸球 多米诺骨牌 信息传递 烽火台 数学归纳法的标准形式 也称第一数学归纳法 设P n 是关于自然数n的命题 若10 奠基 P n 在n 1时成立 20 归纳 在P k k是任意自然数 成立的假定下可以推出P k 1 成立 则P n 对一切自然数n都成立 证明思路 设集合M是使P n 成立的所有自然数n组成的集合 证M N即可 例1 有2n 1个飞机场 每个机场都有一架飞机 各个机场间的距离都不相等 让所有的飞机一起起飞 飞向最近的机场降落 求证 必存在一个机场 没有飞机降落 1当n 1时 3个机场为A B C 且BC AC BC AB则B C间的飞机必定对飞 于是不管A机场的飞机飞向B还是C机场 A机场都没有飞机降落 2假设n k时命题成立 则当n k 1即2k 3个机场时 由于各机场间距离都不相等 必有两个机场间距离最短 这两处的飞机对开 将这两机场 撤出 由假设 剩下的2k 1个机场中 必存在一个机场P没有飞机降落 再把 撤出 的两机场复归 则机场P仍无飞机降落 得n k 1时命题仍成立 数学归纳法的 变着 数学归纳法的多种形式 第一数学归纳法的变着第二数学归纳法反向数学归纳法跷跷板数学归纳法等 第一数学归纳法的 变着 跳跃数学归纳法 其步骤是 1 p 1 p 2 p h 成立 2 假设p k 成立 k为任意自然数 可以推出p k h 成立 则对一切自然数p n 成立 跳跃数学归纳法运用 试证用面值为3角和5角的邮票可支付任何n n 7 n是正整数 角的邮资 改变3与5 可造出类似的问题 第二数学归纳法 推理格式 设P n 是关于自然数n的命题 1 奠基 P 1 成立 2 归纳 假设当n k k为任意自然数 时P 1 n k 成立能推出P k 1 成立 则P n 对一切自然数n都成立 与第一数学归纳法比较 有何不同 它的归纳假定强化了 第二数学归纳法的理论基础 用反证法 假设P n 不是对一切自然数都成立 则使P n 不成立的所有自然数组成的集合M非空 由最小数原理 M中必有最小数h 因为P 1 成立 故1不属于M 所以h 1 故令h k 1 于是p 1 p 2 p k 都成立 于是由2 知p k 1 成立 但由h属于M 故p k 1 不成立 矛盾 所以P n 对一切自然数都成立 若an 0 且 有an n成立吗 第二数学归纳法例举 有两堆棋子 数目相等 两人玩耍 每人可以在一堆里任意取几棵 但不能同时在两堆里取 规定取得最后一棵者胜 问先取者得胜 还是后取者可以得胜 试加以证明 解 当n 1时 必是后取者得胜 猜测 后取者可以得胜 假设n k时命题成立 对于n k 1 当先取者在一堆里取m 1 m k 1 颗时 后取者在另一堆里也取m颗 两堆棋子都是 k 1 m 颗 这样就变成了n k 1 m的问题 按归纳假设 后取者得胜 即n k 1命题也成立 证明了对于所有正整数n 后取者按上述策略都可以得胜 思考 两堆棋子的数目不同呢 反向数学归纳法及其理论依据 设p n 是关于自然数n的命题 若1 p n 对无限多个自然数n成立 2 假设p k 1 成立可推出p k 成立 则命题对一切自然数n都成立 证明 若有p a 不成立 令B b b a且p b 成立 由1 知B不是空集 令m是B中的最小值 由2 得p m 1 成立 显然m 1 a 若m 1 a 则m 1属于B 与m的最小性矛盾 若m 1 a 则与p a 不成立矛盾 得证 走楼梯 问题 某人要走一架n个台阶的楼梯 某人每步能向上走1个台阶或2个台阶 un表示该人从地面走到第n个台阶时所有不同的走法种数 求un 按第一步的走法分类 分走1阶或走2阶两类 un un 1 un 2 n 3 u1 1 u2 2 斐波那契数列 解 证明 斐波那契数列中有 证明 斐波那契数列中有 命题An 命题Bn 跷跷板数学归纳法 其原理是 可以推广到三个甚至上个以上的命题 1 A1真 B1真 2 Ak真 且Bk真 推出Ak 1真 同时Bk真 且Ak 1真 推出Bk 1真 则An Bn对所有的自然数n都真 斐波那契数列的一些性质的模型 实数系的连续归纳法 设Px是涉及一个实数x的命题 如果 有某个x0 使对一切x0 使Px对一切x y y也真 那么 对一切实数x Px真 作业 P63T6 T7 思考题 1 问对于怎样的正整数n 给定的正方形总可以分成n个互不重叠的小正方形 设p1 p2 pn 是由小到大排列的素数数列 试证 反向数学归纳法运用 已知f x 是定义在N上 又在N上取值的函数 并且1 f 2 2 2 对任何m n N 有f mn f m f n 3 当m n时 f m f n 求证f x x在N上恒成立 跷跷板数学归纳法运用 设三角形的三边长a b c均为正整数 记a b c n的三角形个数为Sn 求证 对所有正整数k 有S2k 1 k