多米诺骨牌上的数学-数学归纳法

1、多米诺骨牌上的数学数学归纳法五十多年前, 清华高校数学系赵访熊教授在给高校一年级同学讲高等数学课,总要先讲讲数学的基本概念和方法,他在讲解数学归纳法的时候,先讲了这样一个故事：某主妇养小鸡十只,公母各半； 她预备将母鸡养大留着生蛋,公鸡就养到一百天就间续杀以佐餐；每天早晨她拿米喂鸡；到第一百天的早晨,其中的一只公鸡正在想：“ 第一天早晨有米吃,其次天早晨有米吃, 第九十九天早晨有米吃,所以今日,第一百天的早晨,一定有米吃；” 这时,该主妇来了,正好把这只公鸡抓去杀了；这只公鸡在第一百天的早晨不但没有吃着米, 反而被杀了, 虽然它已有九十九天吃米的体会,米吃；但不能证明第一百天肯定有（赵访熊,

2、1908 年 1996 年,我国最早提倡和从事应用数学与运算数学的教学与讨论的 学者之一；）赵先生把这只公鸡的推理戏称为“ 公鸡归纳法”；明显这是一种错误的不完全归纳法；我们常常会遇到涉及全体自然数的命题,对待这种问题, 假如要否定它, 你只要能举出一个反例即可； 假如要证明它,由于自然数有无限多个,如是一个接一个地验证下去,那永久也做不完； 怎么办？数学家想出了一种特别重要的数学方法来解决这类问题,那就是数学归纳法；【数学史话】欧几里得的开端实际上, 人们很早就遇到了无限集合的问题,而当时具体的推导或运算都只是针对有限对象, 实施有限次论证； 怎样在具体的推导或运算中把握无限的难题,很早就摆

3、在数学家面前了；（欧几里得,公元前 330 年 公元前 275 年,古希腊宏大的数学家,被称为数学之父）最先是古希腊数学家欧几里得在他的几何原本中采纳了近似于数学归纳法的思想；1 该书第九卷第 20 命题是： “素数比任何给定的一批素数都多；”欧几里得在证明这一命题时采纳了特殊的“ 几何 ” 方式,他把数视为线段：设有素数 a、b、c,另设 dabc 1,就 d 或是素数或不是素数；假如 d 是素数,就 d 是与 a、b、c 三者都不同的素数；如 d 不是素数,就它必有素因数e,并且 e 与 a、b、c 都不同,所以肯定有比给定的素数更多的素数；这一证明里隐涵了：如有 n 个素数,就必定存在

4、n1 个素数,因而自然推出素数有无限多个；这里一种试图用有限推导把握无限的作法；虽然它不是很完善,但由于它隐涵着这个命题,人们仍是普遍接受了它；这可以说是数学归纳法思想产生的早期,人们沟通有限和无限的一种初步的尝试；帕斯卡的工作欧几里得之后, 好像是由于数学的进展长期没有进一步提出涉及无限集合的问题,所以在漫长的 18 个世纪中没有人在这个问题上前进一步；直到 16 世纪,一位意大利数学家毛罗利科在他的 算术 一书中明确地提出了一个“递归推理 ”原就, 并提出了一个例子：“证明1 3 5 （ 2k 1） k2 对任何自然数k 都成立 ” ；他用这一例子来说明这一原就的应用；不过他并没有对这一原

5、就作出清楚的表述,所作的证明也仅限于对 k2、3、4 时进行的运算； 他仍像欧几里得那样,隐涵地表示出原就的必要性；但由于他第一次正式提出这一原就,并以例子说明,所以人们认为毛罗利科是第一个正式应用数学归纳法的人；明确而清楚地阐述并使用了数学归纳法的是法国数学家、物理学家帕斯卡； 帕斯卡发觉了一种被后来称作“帕斯卡三角形 ”的数表,即二项绽开式系数表,中国称为“贾宪三角形 ” ；它是宋代贾宪于公元 11 世纪最先发觉的；而帕斯卡在讨论证明这个“ 算术三角形 ”等三个命题时,他最先精确而清楚地指出了证明过程所必需且只需的两个步骤,他称之为第一条引理和其次条引理；第一条引理该命题对于第一个底（即n

6、 1）成立,这是很明显的；其次条引理假如该命题对任一底（对任一 n）成立, 它必对其下一底 （对 n1）也成立；由此可见,该命题必定对全部 n 值都成立；数学归纳法证明的第一个数学命题；帕斯卡的证明方法正是现在的数学归纳法,他所提出的两个引理就是数学归纳法的两个步骤,他在 1654 年写出的著作论算术三角形中做了详尽的论述；因此,在数学史上,人们认为帕斯卡是数学归纳法的创建人；（布莱士 帕斯卡（Blaise Pascal ）公元 1623 年 6 月 19 日诞生于多姆山省奥弗涅地区的克莱蒙费朗,法国数学家、物理学家、哲学家、散文家；）2 归纳法的完善由于帕斯卡的时代,尚没有建立表示自然数的符

7、号,所以帕斯卡证明的其次步仍然只能以例子来陈述；1686 年,瑞士数学家 J伯努利提出了表示任意自然数的符号,在他的猜度术一书中,给出并使用了现代形式的数学归纳法；这样, 数学归纳法开头得到世人的承认并得到数学界日益广泛的应用；后来, 英国数学家德 摩根给定了 “数学归纳法（ mathematical Induction ）的名称；1889 年,意大利数学家皮亚诺建立自然数的公理体系时,把数学归纳法作为自然数的公理之一（称为递归公理或数学归纳法公理） 确立起来； 这才为数学归纳法奠定了坚实的理论基础；那么数学归纳法与人们通常说的规律学中的“ 归纳法 ” 有什么关系呢？对这一问题曾有过数学归纳法

8、是归纳方法仍是演绎方法的争辩；这主要缘于“数学归纳法 ” 的名称有误,实际上,它应称为“递归方法” 或“ 递推方法 ” ,是一种 “ 从 n 过渡到 n 1” 的证明方法,与规律学中的归纳法没有什么关系；严格地说,它倒属于演绎方法：递归公理是它的一个大前提以有限把握无限；数学归纳法中的递推思想在我们的生活实践中常常会遇到；比如家族的姓氏, 我们知道通常按父系姓氏遗传,即下一代的姓氏随上一代父亲的姓确定,并且知道了有个家族第一代姓李,只要明确了这两点,我们就可以得出结论：这个家族世世代代都姓李；再比如,我们常常玩的多米诺骨牌,把骨牌按肯定的间隔距离直立起来,假定将其中任何一块推倒都可以波及下一块

9、,这时你假如推倒了第一块,后面无论有多少块骨牌,确定全部会倒掉；这两个事例告知我们这样一个道理：在证明一个包含无限多个对象的问题时,不需要也不行能逐个验证下去,只要能明确确定两点：一是问题所指的头一个对象成立,二是假定某一个对象成立时, 就它的下一个也必定成立,这两条合起来就足以证明原问题；数学归纳法就是在这个简洁道理的基础上抽象而成的,它的现代表述是： 证明关于自然数 n 的命题 P（n）,只要：一证明 P（l）为真；二假设 P（ k）为真,就 P（k l）为真；两项都得到证明,就 P（n）为真；依靠于自然数的命题在数学中普遍存在,用数学归纳法证明这类命题,两步缺一不行；第一步叫奠基, 是基

10、础； 其次步叫归纳, 实际上是证明某种递推关系的存在；这是以有限来把握无限,通过有限次的操作来证明关于无限集合的某些命题；数学界把数学归纳法视为沟通有限和无限的桥梁,假如没有这个桥梁,很难想象人类如何认识无限集合问题,数学的进展也将会大打折扣；所以,数学家特别重视并常常使用它,正是这座桥梁使人类通向了熟悉的彼岸！【数学应用】数学归纳法在概率论方面的应用在概率问题中常会遇到一些与试验次数有关的重要结论,这些结论在使用数学归纳法证明时, 常常需要协作使用全概率公式,从而使概率论中的数学归纳法具有自己的特色下面我们一起来看一个具体的例子；3 例 1. 设有n个罐子,在每个罐子里各有m 个白球和 k

11、个黑球,从第一个罐子中人任取一球放到其次个罐子里,并以此类推,求从最终一个罐子里取出一个白球的概率令H解：先探究规律,设n2；H2“ 从其次个罐子中取出一个球,是1“ 从第一个罐子里取出一个球,是白球”白球” m1明显 PH mk所求概率 PH P H1PH2H +PH PH H mm1kmmmkmk1mkmk1mk这恰与n1时的结论是一样的,于是可以预见,无论n 为什么自然数,所求的概率都应是mk, 就 当nt1时 , 有PH t1P HtPH t1Ht+PHtPH tmmm1kmmH mkmk1mkmk1mk于是,结论PHnmmk对全部自然数都成立数学归纳法在生物学中的应用数学归纳法不仅在

12、数学中有广泛的应用,在生物学应用数学归纳法也有重要的意义；下面我们一起来讨论一个生物学中的例子；例 2. 求含 n 对等位基因的杂合子F 产生配子的种类T n 对等位基因位于n 对同源染色体上 ；解：当杂合子 1F 只含 1 对等位基因时,如 Aa ,就它只能产生 2 种配子,即 A、a当杂合子 F 含 2 对等位基因时,如 AaBb ,就它只能产生 4 种配子,即Ab、aB、AB、ab当杂合子 F 含 3 对等位基因时,如 AaBbCc ,就它只能产生 8 种配子,即AbC、aBC、ABC、abC、Abc、aBc、ABc、abcn由此猜想,含 n 对等位基因的杂合子 1F 产生配子的种类数

13、T n 2用数学归纳法证明如下：4 （1）当n1时,前面已证2 k,即 AaBbCcKk （共 k 对等位基因）可产生2 k 种配（2）k 时,T k假设 n子那么当nk1时, AaBbCcKkMm（共 k+1 对等位基因）可产生2 k 种含M 的配子,也可产生2 k 种含 m 的配子；即 AaBbCcKkMm 可产生2k2k2 k1种配子；由（ 1）（2）可知,含n 对等位基因的杂合子F 产生配子的种类数T n2n【思维导航】假使我们证得特殊命题 P（）,P（ ）成立,用不完全归纳法,断言对于全部自然数 n ,命题 P n（ ）都成立；这样的论断是不行靠的；而用完全归纳法进行列举,往往又不行

14、能；数学归纳法正是解决这类冲突的一种推理方法,法,但又不能和归纳推理等同；数学归纳法从本质上说是一种演绎推理的方一个和自然数有关的命题,我们记（ ）,假如它实际上是一个包含很多个特殊命题,这命题序列即 P 1, P 2, , P n, ,而且每一个特殊命题均可由它的前一个命题导出；对于这类命题的证明,我们通常要用到数学归纳法；一、数学归纳法及其步骤 : 设 P n（ ）是一个表示与正整数 n 有关的命题；*归纳奠基：当 n n （n 0 N ）时, P n（ ）成立；递推的依据：假设当 n= k k n 0）时, P n（ ）成立,由此可推出（ ）在 n= k + 1时成立,那么 P n（ ）

15、对一切正整数 n n 时都成立；特殊要说明的是, 数学归纳法中的两步缺一不行,第一步是数学归纳法的推理的基础和依据, 假如缺了第一步,即使证明白其次步,命题也不肯定成立；其次步在命题序列中建立了推理链的关系,在 P n 0 成立的前提下,保证了命题序列中递推关系的成立,使推理链一环扣一环,直至对不小于 n 的全部自然数 n,（ ）都成立；二、数学归纳法证明的典型问题1. 有关代数恒等式的证明等式的证明, 我们一般采纳的方法是在等式两边同时加上或同乘以第k1 项,然后适当变形可证得5 例 1. 求证： coscos 2cos 22cos 2n1sin2n（sin0）12nsin证明：（1）当n1

16、 时,左边cos,右边sin 22 sincoscos,所以当n2 sin2sin时,命题成立（2）假设当nkk1 时命题成立,即coscos 2cos22cos 2k1sin2k,将此式的两边同时乘以cos2k,得2ksincoscos 2cos 22cos 2k1cos2ksin2kcos2k2ksin2sin2kcos 2ksin2k122ksin2k1sin所以当nk1 时命题成立综合（1）（2）可知对于任意自然数命题都成立2. 有关数列命题的证明利用数学归纳法证明数列问题是高中数学最常见问题,下面我们以等差数列的前n 项和的公式为例来看看如何应用数学归纳法例 2.求证：等差数列前n

17、项和的公式S nna 11n n1d,其中a 为首项, d 为2公差S证明：（ 1）当n1,S 1a1,等式成立k1（2）假设当nkk1 命题成立,即S k1ka 11kk1 d,那么,S2kak1ka 11k k1da 1（k1）d1a 11k k1dk22所以当nk1 时命题成立综合（1）（2）可知对于任意自然数命题都成立3. 有关不等式的证明要由“ 假设不等式” 成立推正到“ 目标不等式” 成立,可先尽早使用“ 假设不等式”,再利用帮助条件通过合理的放缩,逐步向“ 目标不等式” 靠近例 3.证明不等式：11 21 312n （nN ）n证明：（1）当n1时,左边1,右边2,左边右边,不等

18、式成立6 （2）假设当nkk1 不等式成立,即111122kk1023k当nk1 时,就1111112k1123kkk（现关键证明2kk112k1）2k1kk11k2k1122kk11kk1k12k112k1,即当nk1 时,不等式成立k综合（ 1）（2）可知对于任意自然数不等式都成立等价转化,降低难度当给出的不等式不简洁直接用数学归纳法证明时,可以对命题进行等价转化,化归为证明相对简洁的不等式4.应用数学归纳法证明整除问题应用数学归纳法证明整除问题,是数学归纳法的重要应用之一这类问题涉及到整除性的学问,假如 a 能被 c 整除,那么 a 的倍数 ma 也能被 c 整除,假如 a 、 b 都能

19、被 c 整除,那么它们的和或差 a b 也能被 c 整除,从整数的基本入手,通过添项去项进行配凑,使之能够获证例 4 证明 f n 5 n 12 3 n1 能被 8 整除证明：（1）当 n 1 时,f n 5 02 3 11 8 明显能被 8 整除,命题成立k 1 k（2）假设当 n k 时,原命题成立,即 f k 5 2 3 1 能被 8 整除,那么,当k k 1 k 1 k k kn k 1 时,f k 1 5 2 3 1 5 5 1 6 3 4 3 4 3k 1 k k k5 5 5 2 3 5 4 4 3 5 f k 4 3 1 这里的第一项由归纳假设能被8 整除,其次项中 3 为奇数

20、,就 k3 k1 为偶数,故其次项 4 3 k 1 能被 8 整除,由整除性质可知,它们的差也能被 8 整除,这就是说：当 n k 1 时命题也成立即原命题对于所有自然数 n 都成立数学归纳法在一些困难的问题中发挥着主要作用,它不仅在中学数学中有用,在我们的7 基础学科： 数学分析高等代数等学科中也发挥着其作用因此, 数学归纳法不仅贯穿于我们数学的各门学科中, 而且在我们的日常生活中也起着不同凡响的正如华罗庚老先生在其 数学归纳法一书中指出的那样：数学归纳法正是表达了人的熟悉从有限到无限的飞跃 . 在人类数学的进步中起着特别广泛的作用【拓展提升】数学归纳法是用于证明与正整数 n 有关的数学命题

21、的正确性的一种严格的推理方法在数学学习, 特殊是竞赛中占有很重要的位置那么数学归纳法除了我们讨论的这种形式,仍有没有其他形式呢？1数学归纳法的基本形式（1）第一数学归纳法设Pn是一个与正整数有关的命题,假如nk1时,P n也成立,那么,依据当nn0（n0N）时,Pn 成立；假设nkkn 0,kN成立,由此推得对一切正整数nn0时,Pn 成立（2）其次数学归纳法设Pn是一个与正整数有关的命题,假如nk1 时,P n也成立,那么,依据当nn0（n0N）时,Pn 成立；假设nkkn0,kN成立,由此推得对一切正整数nn0时,Pn 成立2数学归纳法的其他形式（1）跳动数学归纳法当nn,12,3,l时,

22、P 1 ,P2 ,P3 ,k,Pl成立,也成立,那么,依据对一假设k时P k成立, 由此推得nl时,Pn 切正整数n1时,Pn 成立（2）反向数学归纳法设Pn是一个与正整数有关的命题,假如nk1 时命题Pk1 也成立,那么依据Pn对无限多个正整数n 成立；假设nk时,命题Pk成立,就当8 对一切正整数n1时,Pn成立3应用数学归纳法的技巧n（1）起点前移：有些命题对一切大于等于1 的正整数正整数n 都成立,但命题本身对,0 也成立,而且验证起来比验证n1时简洁,因此用验证n0成立代替验证n1同理,其他起点也可以前移,只要前移的起点成立且简洁验证就可以因而为了便于起步,有意前移起点（2）起点增多

23、：有些命题在由nk向nk1 跨进时,需要经其他特殊情形作为基础,此时往往需要补充验证某些特殊情形,因此需要适当增多起点（3）加大跨度：有些命题为了削减归纳中的困难,适当可以转变跨度,但留意起点也 应相应增多（4）挑选合适的假设方式：归纳假设为肯定要拘泥于“ 假设nk时命题成立” 不行,需要依据题意实行第一、其次、跳动、反向数学归纳法中的某一形式,敏捷挑选使用（5）变换命题：有些命题在用数学归纳证明时,需要引进一个帮助命题帮忙证明,或 者需要转变命题即将命题一般化或加强命题才能满意归纳的需要,才能顺当进行证明5归纳、猜想和证明 在数学中常常通过特例或依据一部分对象得出的结论可能是正确的,也可能是

24、错误的,这种不严格的推理方法称为不完全归纳法不完全归纳法得出的结论,只能是一种猜想,其正确与否,必需进一步检验或证明,常常采纳数学归纳法证明不完全归纳法是发觉规律、解决问题极好的方法【数学观赏】帽子嬉戏与数学归纳法 华罗庚先生 1963 年写了一本数学归纳法小册子,其中讲到如何建立归纳假设；他 从一个好玩的数学嬉戏开头：问题是这样的： 有一位老师, 想辨别出他的三个满意门生中那一个更聪慧一些,它采纳 了以下的方法；事先预备好 5 顶帽子,其中 3 顶是白的, 2 顶是黑的；在试验时,他先把这 些帽子让同学们看了一看,然后要他们闭上眼睛,替每个同学戴上一顶白色的帽子,并且把2 顶黑帽子藏了起来,

25、最终再让他们张开眼睛,请他们说出自己头上戴的帽子,到底是哪一 种颜色；相互看了一看,犹豫了会儿,然后他们异口同声地说,自己头上戴的是白色的帽子；他们是怎样推算出来的呢？他们怎样能够从别人头上戴的帽子的颜色,正确地推断出自己 头上戴的帽子的颜色的呢？建议同学们读到这儿,临时把书搁下来,自己想一想；能够想出来吗？假如一时想不 出,可以多想一些时候；现在,谜底揭晓一下：甲、乙、丙三个同学是怎样想的；甲这样想： 假如我头上戴的是黑帽子,那么乙肯定会这样想：假如我头上戴的是黑帽 子,那么丙肯定会这样想：（甲乙两人都带了黑帽子,而黑帽子只有两顶,所以自己头上戴 的肯定是白帽子； ）这样丙就会脱口而出地说出

26、他自已头上戴的是白帽子；但是他为什么踌躇？可见自己 头上戴的是白帽子；假如这样乙也会脱口而出地说他自己头上戴的是白帽子；但是他为什么也要犹豫呢？可见自己 头上戴的不是黑帽子； （为了便利阅读,现将文中显现的括号说明一下：里的是甲的想法,里的是甲设想乙应当有的想法, （）里的是甲设想乙应当为丙设想的想法）经过这样摸索,于是三人都推出了自己头上戴的是白帽子；读者读到这儿,请再想一9 下,想通了没有？有些伤脑筋吧！学过数学归纳法的人会怎样想呢？他会先退一步,原始而不失去重要性的地方,是学好数学的一个诀巧！（善于 “退 ”,足够地 “退” ,“ 退”到最）不考虑三个人而仅仅考虑两个人一顶黑帽子的问题；

27、这个问题谁都会解,黑帽子只有一顶,我戴了,他马上会说：“自己戴的是白帽子 ”；但是,他为什么会犹豫呢？可见我戴的不是黑帽子而是白帽子；这就是说, “两个人,一顶黑帽子,不管多少（当然要不少于 一个轻而易举的问题；2）顶白帽子 ” 的问题,是现在我们来解上面这个复杂的：“三个人,两顶黑帽子,不管多少（当然要不少于3）顶白帽子 ”的问题也就简洁了；为什么呢？假如我头上戴的是黑帽子,那么对于他们两个人 来说,就变成 “ 两个人,一顶黑帽子”的问题,这是他们两人应当马上解决的问题,是不必踌 躇的；现在他们在犹豫,就说明白我头上戴的不是黑帽子而是白帽子；这里可以看到,学会了数学归纳法,就会得运用 一顶黑

28、帽子,把它转化为一个简洁的问题；“归纳技巧 ”从原先问题里减去一个人、倘使我们把原先的问题再搞得复杂一些：“ 四个人,三顶黑帽子,如干（不少于 4）顶白帽子 ”；解这个问题,假如仍然用我们开头时的表达方法,那么肯定要说成：“ 甲想 .等等” ；这样讲起来多费事,简直象“拗口令 ”,使人不易听清,不易搞懂；但是把握了数学归纳法,善于 “ 退”,那就只要用几句话就可了事,“ 假如我头上戴的是黑帽子,那么对他们三 个人来说,是 三个人,两顶黑帽子,如干顶白帽子 的问题；这个问题他们马上会解决而不 必犹豫；现在他们要犹豫,正是说明我戴的不是黑帽子而是白帽子；” 换句话说, “假如我头 上戴的是黑帽子” 就是这里的归纳假定；岂特四个人三顶黑帽子,即使象“ n个人, n-1 顶黑帽子,如干（不少于 n顶白帽子 ” 这 样复杂的问题,我们也可以很简洁地解决了；由于当 n=2 时已经解决了,假设当 n=k 时问 1 人戴的是黑帽子,就变成 n=k 的问题,大家都会 题已经解决,那么当 n=k+1 时,只要有 应用数学归纳法, 他们应当都说出他们自己头上戴的是白帽子,但是他们要犹豫,所以这个 人就可以判定出自己头上戴的是白帽子；