数学归纳法原理及其应用举例
目录
中文摘要
英文摘要
1 引言 (1)
2 数学归纳法原理 (1)
2.1 良序原理 (1)
2.2 数学归纳法 (2)
2.3 第二数学归纳法 (3)
2.4 数学归纳法的有效性 (4)
3 数学归纳法应用举例 (4)
3.1 数学归纳法在解题和证明中的一些应用 (4)
3.2 数学归纳法在递归定义上的应用 (10)
3.3 数学归纳法在递归算法上的应用 (13)
参考文献 (17)
数学归纳法原理及其应用举例
摘要：数学归纳法原理是一种有效的证明方法.本文将介绍数学归纳法及其等价形式，并证明为什么它们是有效的.特别地，我们将用大量各种不同类型的例子来说明其应用。这些例子有的来自于集合论，数论，有的来自于计算机科学等.
关键词：良序原理，数学归纳法，第二数学归纳法，递归算法.
Abstract: The principles of mathematical induction provide effective ways for valid arguments in mathematical proofs. This thesis will present these principles and their other equivalent forms, and will show why they work and particularly will show how they work by examples from diversified settings or areas of mathematics, e.g. set theory, number theory, computer algorithm, and so on.
Key words:The well-ordering principle, the first principle of mathematical induction, the second principle of mathematical induction, recursive algorithm.
1 引言
首先使用数学归纳法的是意大利数学家和工程师马奥罗修勒斯（Francesco Maurocyulus，1494-1575），他在1575年的著作《算术》（Arithmetica）中，用数学归纳法证明了前n个正奇数之和是2n.帕斯卡（Blaise Pascal,1623-1662）在他关于算术三角形（现在称为帕斯卡三角形）的著作中使用了归纳法.在他1653年的著作《论算术三角形》（Traite du triangle arithmetique）中，在证明用来定义他的三角形的基本性质时，帕斯卡清晰地解释了归纳法.德摩根在1838年的一篇关于证明方法的论文中，把这个原理命名为“数学归纳法”.
前n个正奇数之和的公式是什么？对1
n=，2，3，4，5来说前n个正奇数之和是=，134
11
++=，
+=，1359
++++=
135716
+++=，1357925
根据这些值，有理由猜测前n个正奇数之和是2n.假如事实上这个猜测是正确的，我们就需要一种方法来证明这个猜测是正确的.数学归纳法是证明这种类型的断言的极为重要的证明技术.
2 数学归纳法原理
2.1 良序原理
所有数学都始于计数，计数就是把要计数的对象集合与几个起始自然数（或计算值）：1,2,3,4,5...一一对应的过程.我们用N表示自然数这个无限集合，这里值得注意的是关于N的定义并未达成共识，有些数学家把0也归入N.但这两种不同定义并不会引起太大的冲突，哪一种使用方便即可选择哪一种.
自然数N的一个基本性质是良序性，下面将对自然数的良序性进行形式化的论述，并且把它作为一个关于N的公理.对于任何系统，公理是无需证明即为真的命题.为了对一个系统（这里指自然数）进行推理，首先需要对该系统做一些假设.尽管这些基本的
假设常常不容易一眼就看出，但它应该是“合理的”和“显而易见为真的”.
良序原理：自然数集N 的每个非空子集都有一个最小元素.
显而易见，自然数N 的任何子集都可以通过列出实际元素的方式给定，即使对于不易直接定义的集合，该定理依然有效.例如，当x 和y 可取任意整数时，考虑1228x y +所表示的所有自然数集合.从定义看该集合的范围并不明显，但是根据良序原理，由于该集合非空（注意这很重要），集合中必有一个通过该方式表示的最小自然数.（当然，求具体的最小自然数的值是另外一回事.注意良序原理保证有一个最小数存在，但绝对没说如何去计算它.）
例2.1.1 用良序原理证明算法的正确性.整除算法说：若a 是整数而且d 是正整数，则存在唯一的整数q 和r 满足0r d ≤<和a dq r =+.
证明 设S 是形如a dq -的非负整数的集合，其中q 是整数.这个集合非空，因为dq -可以任意大（取q 是绝对值很大的负整数）.根据良序性，S 有最小元0r a dq =-.
整数r 非负而且r d <.若不是这样，则S 里存在更小的非负整数，即0(1)a d q -+.为了看出这一点，假设r d ≥.因为0a dq r =+，所以00(1)0a d q a dq d r d -+=--=-≥.因此，存在满足0r d ≤<的整数r 和q .证明q 和r 都是唯一的，此处略.
良序原理允许我们证明最有效的一个证明方法，即数学归纳法定理. 2.2 数学归纳法 对任何正整数n ，
21
5811...(32)(37)2
n n n +++++=
+ 因为存在无限多个正整数，所以，在证明这个断言时，不能通过对n 的每个值逐一验证等式是否成立.有一种规范的方法可用来证明命题对所有的正整数都成立，这种方法称为数学归纳法原理.
定理 2.2.1 假设要证明的命题能写成0()n n P n ?≥，其中0n 是某个固定整数，即：
假设希望证明对所有整数0n n ≥都有()P n 为真，那么如下方法可以说明如何做到这一点.假设（a ）0()P n 为真,和(b)如果对任一0k n ≥只要()P k 为真，那么(1)P k +也一定为真.于是对所有0n n ≥，()P n 为真.这种方法称作数学归纳法原理.
因此，用数学归纳法原理证明命题：0()n n P n ?≥为真，必须首先用直接法证明第一个命题0()P n 为真，称其为归纳法的基础步骤，并且通常来讲该步是非常容易的.然后必须证明对0n n ≥的任何选择，()(1)P k P k ?+是一个重言式.因为一个蕴涵为假的惟一情况是如果前提为真而结论为假，做这一步通常是证明如果()P k 为真，那么(1)P k +也一定为真.注意，它同假设对某个k 值()P k 为真不一样.这一步称作归纳步骤，并且某些工作通常要求证明蕴涵恒为真.
2.3 第二数学归纳法
与上述数学归纳法略有不同的形式在某些证明当中更易于使用.第二数学归纳法或强归纳法中，其归纳步骤是证明
000()(()(1)(2)...())(1)k P n P n P n P k P k ?∧+∧+∧∧?+
是一个重言式.同前面一样，需要检验的唯一情况是如果每个()P j ，0,...,j n k =为真，那么(1)P k +为真.强归纳法与数学归纳法是等价的，在一个证明中使用哪一个取决于方便性.
例 2.3.1 证明：每个正整数1n >能惟一地写成12
12...s a a a s p p p ，其中i p 是素数且
12...s p p p <<<.
证明（用强归纳法）
基础步骤 这里02n =，显然(2)P 为真，因为2是素数.
归纳步骤 使用(2)P ，(3)P ，…，()P k 证明(1)P k +：1k +能惟一地写成1212...s a a a s p p p ，
其中i p 是素数且12...s p p p <<<.需要考虑两种情况：若1k +是一个素数，则(1)P k +为真.若1k +不是素数，则1k lm +=，2l k ≤≤，2m k ≤≤.利用()P l 和()P m ，得1k +=lm =
121212
121212.........s u s b c a b b c c a a s u s q q q r r r p p p =，其中每个i j p q =或k r ，12...s p p p <<<.若i k j p r q ==，
则i j k a b c =+，否则i j p q =且i j a b =或者i k p r =且i k a c =.因为l 和m 的因子分解是惟一的，所以1k +的因子分解也是唯一的.
2.4数学归纳法的有效性
为什么数学归纳法是一种有效的证明方法？原因在于良序原理.假定知道(1)P 为真，而且对所有正整数n 来说命题()(1)P n P n →+为真.为了证明对所有正整数来说()P n 都为真，假定至少存在一个()P n 为假的正整数.那么使()P n 为假的正整数S 非空.因此，根据良序性，S 有一个最小元，把它表示成k .可以知道k 不是1，因为(1)P 为真.因为k 是正的而且大于1，所以1k -是一个正整数.另外，因为1k -小于k ，它不属于S ，所以
(1)P k -必然为真.因为蕴涵式(1)()P k P k -→也为真，所以实际情况必然是()P k 为真.
这与对k 的选择相矛盾.因此对每个正整数n 来说()P n 必然为真.
3 数学归纳法应用举例
3.1 数学归纳法在解题和证明中的一些应用
定理3.1.1 每一个大于1的整数要么是素数，要么是若干素数的乘积.
证明：设n 为大于1的整数.证明将采用强数学归纳法原理，对n 作归纳.因为2是一个素数，所以命题对2n =是正确的.
假设对某个整数1k >，当2,3,...,n k =时，命题为真.下面要证明1k +要么是素数，要么是若干素数的乘积.如果1k +是素数，那么证明已经完成.所以，假设1k +不是素数.于是，存在一个既不是1也不是1k +的正整数p ，p 整除1k +.所以，
1
k q p
+=是整数，且1q ≠（否则1p k =+），1q k ≠+（否则1p =）.因此，p 和q 都是2到k 之间的整数（含2和k ）.所以可以对p 和q 运用归纳假设，即p 和q 不是素数就是若干素数的乘积，从而1k pq +=是若干素数的乘积.这就完成了归纳步骤，因此完成了定理的证明.
注意，定理3.1.1虽然说明了大于1的正整数不是素数就是素数的乘积，但这个定
理并不能帮助判断是两种情形中的哪一种.特别地，定理3.1.1也不能实际地找到特定的正整数的素数因子.
例3.1.1 实验室里有容积相同的量杯盛着各种不同的液体，此外还有一只容积相同的
空杯.证明：可以通过有限次混合手续，使它们成为成份相同的溶液，此外还余一个空量杯.
分析：表面上看本题与数学归纳法没有联系，但若我们引入一个整数参数（原有溶液的杯数），我们就可以考虑应用数学归纳法.
事实上，不妨设有n 杯各种不同的溶液，显然1n =时命题成.立假设n k =时命题成立,即k 杯溶液可以通过有限次混合手续，使它们成为成份相同的溶液.此外还有一个空杯，于是当再增加一杯时，我们只需把k 杯已混合好的溶液各倒
1
1
k +杯到空杯中，最后拿增加的那杯溶液去把上述1k +杯液体满，这样我们便得到1k +杯成份相同的液体，此外还有一个空杯，也就是说1n k =+时命题也成立.
上面的分析告诉我们，很多与自然数n 有关的问题都可采用数学归纳法，而一个具体的问题能否用数学归纳法，以及取什么做n ，则取决于能否递推.只要有递推的希望，就不妨一试.
例3.1.2 设1A ，2A ，3A ，…，n A 是任意n 个集合，用数学归纳法证明
11
n n
i i i i A A ==??= ???
（这是德?摩根定律的推广形式.）设()P n 是谓词：对任意n 个集合等式成立.用数学归纳法需证明，对所有1n ≥，()P n 为真.
证明 基础步骤 (1)P 是命题11A A =，这显然成立. 归纳步骤 用()P k 去证明(1)P k +.(1)P k +的左边是
1211...n i k k i A A A A A +=??
= ???
121(...)k k A A A A += 的结合性质
121(...)k k A A A A += 两个集合的德?摩根定律 11k i k i A A +=??
= ???
用()P k 1
1k i i A +== (1)P k +的右边
因此，蕴涵()(1)P k P k ?+的一个重言式，由数学归纳法原理可知对所有1n ≥，
()P n 为真.
例3.1.3 本例将要证明：对于任何正整数n ，如果从22n n ?的棋盘（每行和每列有
2n 个方格）中移去任何一个方格，则剩下的方格可以用若干个L 形构件覆盖，每个L 形
构件覆盖3个方格，如图1所示.
图一
证明 如图2所示，每个1122?的棋盘移去一个方格后，可被一个L 型构件覆盖.因此，结论对于1n =是正确的.
现在假设对于某个正整数k 结论是正确的，即每个22k k ?的棋盘移去一个方格后，可用若干个L 形构件覆盖.下面要证明：任何一个1122k k ++?的棋盘移去一个方格后，可用L 形构件覆盖.如果1122k k ++?的棋盘在横向和纵向上都平分为两部分，就得到4个
22k k ?的棋盘.其中的一个22k k ?被移去了一个方格，而另外3个是完整的，如图所示.
从每个完整的22k k ?的棋盘中移去那个位于原1122k k ++?的棋盘中心位置的方格，如图3所示.由归纳假设知道，图4所示的所有4个移去了一个方格的22k k ?的棋盘都可以被L 形构件覆盖.因此，再用一个L 形构件覆盖原1122k k ++?的棋盘中央的3个方格，就可以用L 形构件覆盖原来的移去了一个方格的
1122k k ++?的棋盘.这就证明了1k +的情况.根据数学归纳法原理，对每一个正整数
n ，任何去掉了一个方格的22n n ?的棋盘都可以用L 形构件覆盖.
图二
图三 图四
定理 3.1.2 设S 是有n 个元素的集合，其中n 是非负整数.如果r 是一个整数，
0r n ≤≤，那么恰好含有r 个元素的S 的子集的数目是
!
!()!
n r n r -.
证明 证明将采用归纳法，对n 作归纳，并从0n =开始.
如果0n =，那么S 是空集，并且r 必定是0.而φ有且仅有一个含0个元素的子集，即它本身，而且，因为0!1=，所以
!0!
1!()!0!0!
n r n r ==-.
所以公式对0n =是成立的.
现在假设公式对某个整数0k ≥是成立的.设S 是含有1k +个元素的集合，比如说
121{,,...,,}k k S a a a a +=.现在要统计S 恰好含有r 个元素的子集的数目，这里01r k ≤≤+.显然，含有0个元素的S 的子集只有Φ.类似地，也只有一个S 的子集含有1k +个元素，即S 本身.对这两种情况，公式都给出了正确的值，因为
(1)!10!(10)!k k +=+-，(1)!
1(1)![1(1)]!
k k k k +=++-+.
设R 是S 的恰好包含r 个元素的任意子集，这里1r k ≤≤.有两种情况需要考虑. 第一种情况：1k a R +?.这时R 是12{,,...,}k a a a 的有r 个元素的子集.根据归纳假设，这样的子集有
!
!()!
k r k r -个.
第二种情况：1k a R +∈.在这种情况下，如果从R 中拿掉1k a +，就得到12{,,...,}k a a a 的含有1r -个元素的子集.根据归纳假设，这样的子集有
!
(1)![(1)]!
k r k r ---个.
把这两种情况合起来，看到S 共有!!
!()!(1)!(1)!
k k r k r r k r +---+个含有r 个元素的子
集.而这个值等于
!(1)!!()!(1)(1)!(1)!k k r k r
r k r k r r r k r -++--+--+
!(1)!!(1)!!(1)!k k r k r
r k r r k r -+=
+-+-+
!(1)
!(1)!k k r r r k r -++=
-+
(1)!
!(1)!
k r k r +=
-+
在公式中，用1k +替换n 就得到这个数，因此公式对于1n k =+是正确的.
所以，根据数学归纳法原理，公式对所有的非负整数n 都是正确的.
例3.1.4 证明：可以仅用4分和5分的邮票来组成等于或超过12分的每种邮资.
证明将要用数学归纳法原理来证明这个结果.然后给出用数学归纳法第二原理的证明.设()
P n是命题：可以用4分和5分的邮票来组成n分邮资.
首先使用数学归纳法原理.
基础步骤：可以用3个4分邮票来组成12分邮资.
归纳步骤：假定()
P n为真，所以可以用4分和5分邮票来组成n分邮资.若至少用了一个4分邮票，则用一个5分邮票代替它，就组成1
n+分邮资.若没有用任何4分邮票，则仅用了5分的邮票来组成n分邮资.因为12
n≥，所以至少用了3个5分邮票.所以4个4分邮票来代替3个5分邮票，就组成了1
n+分邮资.这完成了归纳步骤以及根据数学归纳法原理的证明.
其次，将要使用数学归纳法的第二原理.将要证明可以组成12，13，14和15分邮资，然后证明如何对15
n+分邮资.
n≥来说从3
n-分邮资得出1
基础步骤：可以分别用3个4分邮票，2个4分邮票和1个5分邮票，1个4分邮票和2个5分邮票，以及3个5分邮票，来组成12,13,14和15分邮资.
归纳步骤：设15
n+分邮资，n≥.假定可以组成k分邮资，其中12k n
≤≤.为了组成1
用组成3
n-分邮资的邮票加上一个4分邮票.这完成了归纳步骤以及根据数学归纳法第二原理的证明.
注意例3.1.4说明如何让数学归纳法第二原理适应于处理某些情形，其中仅对充分大的n值来说归纳步骤才是有效的.具体说来为了证明对,1,2,...
n k k k
P n
=++来说()为真，其中k是整数，首先证明(),(1),(2),...,()
++都为真（基础步骤），然后
P k P k P k P l
证明对每个整数1
n≥来说[()(1)(2)...()](1)
∧+∧+∧∧→+为真（归纳步
P k P k P k P n P n
骤）.例如，例3.1.4解答里的第二个证明的基础步骤证明(12),(13),(14)
P都
P P P和(15)
为真.需要分别地证明这些情形，因为归纳步骤证明[(12)(13)...()](1)
∧∧∧→+，
P P P n P n
它仅当15n ≥时才成立.
在下面将要讨论数学归纳法的另外两个重要应用.第一个应用涉及到定义序列而不给出明确的项公式.第二个应用涉及到证明计算机程序是正确的.
3.2 数学归纳法在递归定义上的应用 3.2.1 引言
定义3.2.1 有时难以用明确的方式来定义一个对象.不过，用这个对象来定义它自身，这也许是容易的.这种过程称为递归.
可以用递归来定义序列、函数和集合.例如，对0,1,2,...n =来说用2n n a =来给出2的幂的序列.不过通过给出这个序列的第一项，即01a =，以及从该序列前面一项来求当前项的规则，即对0,1,2,...n =来说12n n a a +=，也可以定义这个序列.
3.2.2 递归地定义函数
定义3.2.2 为了定义以非负整数集合作为其定义域的函数，就要 (1)规定这个函数在0下处的值.
(2)给出从较小的整数处的值来求出当前的值的规则. 这样的定义称为递归定义或归纳定义.
许多函数都可以利用它们的递归定义来研究.阶乘函数就是一个这样的例子. 例3.2.1 给出阶乘函数()!F n n =的归纳定义.
解 可以通过规定阶乘函数的初值，即(0)1F =，并且给出从()F n 求出(1)F n +的规则，来定义这个函数.要得出这个结果，注意通过乘以1n +就从!n 计算出(1)!n +.因此，所需要的规则是(1)(1)()F n n F n +=+.
为了从在例7中求出的递归定义来确定阶乘函数的一个值，比如(5)5!F =，有必要多次使用说明如何用()F n 表示(1)F n +的规则：
(5)5(4)54(3)543(2)5432(1)F F F F F ==?=??=???
54321(0)54321120F =????=????=
一旦(0)F 是出现的唯一的函数值，就不需要任何更多的归约.剩下来要做的唯一事情是把(0)F 的值插入到公式里.
递归地定义的函数是严格定义的.这是数学归纳法原理的一个后果. 例3.2.2 给出0n
k k a =∑的递归定义.
解 这个递归定义的第一步是 0
00
k k a a ==∑,
第二步是 110
n n
k k n k k a a a ++===+∑∑.
在函数的某些递归定义里，规定了函数在前k 个正整数处的值，而且给出了从一个较大的整数之前的部分或全部k 个整数处的函数值来确定在该整数处的函数值的规则.从数学归纳法第二原理可以得出结论说这样的定义产生严格定义的函数.
例3.2.3 斐波那契数012,,,...f f f 是用等式00f =，11f =，以及对2,3,4,...n =来说
12n n n f f f --=+
来定义的.斐波那契数2f ，3f ，4f ，5f ，6f 是什么？
解 因为这个定义的第一部分说00f =和11f =，所以从这个定义的第二部分得出
210101f f f =+=+= 321112f f f =+=+= 432213f f f =+=+= 543325f f f =+=+= 654538f f f =+=+=
可以用斐波那契数的递归定义来证明这些数的许多性质.在下一个例子里给出一个这样的性质.
例3.2.4 证明：每当3n ≥时就有2n n f α->
，其中(1/2α=.
证明 可以用数学归纳法第二原理来证明这个不等式.设()P n 是命题：2n n f α->.想要证明每当n 是大于或等于3的整数时就有()P n 为真.
首先，注意到
32f α<=，24(323f α=<=
所以(3)P 和(4)P 都为真.现在假定()P k 为真，即对所有满足3k n ≤≤的整数k 来说有2k k f α->，其中4n ≥.必须证明(1)P n +为真，即11n n f α-+>.因为α是210x x --=的解（二次方程求根公式说明这一点），所以得出21αα=+.因此，
12333323(1)1n n n n n n n αααααααααα-------=?=+?=?+?=+
根据归纳假设，若5n ≥，则得出
31n n f α-->，2n n f α-> 因此就有
23111n n n n n n f f f ααα---+-=+>+= 由此得出(1)P n +为真，证毕.
注意 归纳步骤证明了每当4n ≥时，从对3k n ≤≤来说()P k 为真的假定就得出
(1)P n +.因此，归纳步骤没有证明(3)(4)P P →.所以，不得不单独证明(4)P 为真.
3.2.3 递归地定义集合
递归定义常常用来定义集合.当这样做时，给出初始的一些元素.然后给出用来从已知属于集合的元素来构造集合的其他元素的规则.以这种方式描述的集合是严格定义的，用它们的递归定义可以证明关于它们的定理.下面是集合的递归定义的一些例子.
例3.2.5 设S 是用 3S ∈ ；
若x S ∈且y S ∈，则x y S +∈
来递归地定义的.证明：S 是被3整除的正整数集合.（注意在这个定义里隐含着假定：
所有属于S的东西都是用S的递归定义里的两个命题来生成的.）
证明设A是被3整除的所有正整数的集合.为了证明A S
=，必须证明A是S的子集而且S是A的子集.为了证明A是S的子集，必须证明被3整除的每个正整数都属于S.将要用数学归纳法来证明它.
设()
P n是命题：3n属于S.基础步骤成立，因为根据S的递归定义的第一部分，?=是属于S的.为了证明归纳步骤，假定()
313
P n为真，即3n属于S.因为3n属于S而且因为3属于S，所以从S的递归定义的第二部分得出333(1)
+=+也属于S.
n n
为了证明S是A的子集，使用S的递归定义.首先，该定义的基础步骤规定3属于S.因为331
=?，所以所有在这个步骤里被规定属于S的元素都被3整除.为了完成这个证明，必须证明所有用该递归定义的第二部分所生成的属于S的元素都属于A.这包括证明每当x和y都是S中的元素并且假定它们都属于A时，就有x y
+属于A.现在若x和y 都属于A，则可以得出3|x和3|y.由整数的可数性的性质，得出3|()
x y
+，证毕.
在上例里集合的递归定义是典型的.首先，给出一组初始元素.其次，给出从已知属于集合的元素来生成新元素的规则.在定义里隐含着只有在初始元素中列出的元素，或者可以用构造新元素的规则来生成的那些元素才属于这个集合.
3.3 数学归纳法在递归算法上的应用
3.3.1 引言
有时可以把带有具体的一组输入的问题的解归约到带更小的一组输入的相同问题
>，就可以归约到求一的解.例如，求两个正整数a和b的最大公因子的问题，其中b a
对更小的整数（即mod
b a和a）的最大公因子的问题，因为gcd(mod,)gcd(,)
=.
b a a a b
当可以实现这样的归约时，就可以用一系列归约来求出原问题的解，直到把问题归约到解是已知的某种情形为止.例如，对求最大公因子来说，归约持续到两个数中较小的一个为零，因为当0
a>时，gcd(,0)
=.
a a
定义3.3.1 若一个算法通过把问题归约到带更小的输入的相同问题的实例，来解决原来的问题，则这个算法称为递归的.
例3.3.1 把线性搜索算法表达成递归过程.
解 为了在搜索序列12,,...,n a a a 里搜索x ，在算法的第i 步比较x 与i a .若x 等于i a ，则i 是x 的位置.否则，对x 的搜索就归约到在少了一个元素的序列（即序列1,...,i n a a +）里的搜索.现在给出递归过程.
设(,,)search i j x 是在序列1,,...,i i j a a a +里搜索x 的过程.过程的输入包括三元组
(1,,)n x .若剩余序列的第一项是x ，或者若序列只有一项并且它不是x ，则过程在这一步
终止.若x 不是这一项而且存在其他的项，则执行同样的过程，但是搜索序列减少一项，它是通过删除搜索序列的第一项而获得的.
递归顺序搜索算法 procedure search (,,)i j x if i a x = then Location:=i else if i j = then location:=0 else
search (1,,)i j x + 3.3.2 递归与迭代
递归定义把在正整数处的函数值表达成在更小的整数处的函数值.这意味着可以设计递归算法来求出递归地定义的函数在正整数处的值.
例3.3.2 下面给出阶乘的递归算法. 阶乘的递归过程
procedure factorial(n :正整数) if 1n = then factorial(n ):=1
else
factorial(n ):=n *factorial(1n -)
存在另外一种方式，从阶乘函数的递归定义求它在整数处的值.代替连续地把计算归纳到在更小的整数处来求函数的值，可以从在1处的函数值开始，连续地应用递归定义来求出在更大的整数处的函数值.这样的过程称为迭代.换句话说，为了用迭代过程求出!n ，从1（即在1处的阶乘函数值）开始，连续地乘以每个小于或等于n 的正整数.
对递归地定义的序列求值的迭代方法，比起使用递归的过程来，常常要求较少量的计算机（除非使用专门的递归机器）.用求第n 个斐波那契数的迭代的递归过程来说这一点.首先给出递归过程.
斐波那契数的递归算法
procedure fibonacci(n :非负整数) if 0n =then fibonacci(0):=0 else if 1n =then fibonacci(1):=1
else fibonacci(n ):= fibonacci(1n -)+fibonacci(2n -)
当使用递归算法求n f 时，首先把n f 表示成12n n f f --+.然后把这两个斐波那契数都换成两
个前面的斐波那契数之和.当0f 或1f 出现时，就直接换成它的值.
注意，在递归的每个阶段，直到获得1f 或0f 为止，需要求值的斐波那契数的个数都一直翻倍.例如，当使用这个递归算法求出4f 时，就必须完成图五里树形图所说明
的全部计算机.这个树包括用4f 标记的根，以及从根到用 图五
两个斐波那契数3f 和2f 标记的顶点的分支，它们出现在4f 的计算的归约里.每个后续的
归约都产生树里的两个分支.当遇到0f 和1f 时，这种分支结束.
现在考虑用下面的迭代过程来求出n f 所需要的计算量.
计算斐波那契数的迭代算法
procedure iterative fibonacci(n :非负整数) if 0n = then y :=0 else begin x :=0 y :=1
for i :=1 to 1n - begin
z :=x y + x :=y y :=z end
end
{y 是第n 个斐波那契数}
这个过程把x 初始化成00f =，把y 初始化成11f =.当经过循环时，把x 和y 之和赋给辅助变量z .然后把x 赋成y 的值，而把y 赋成辅助变量z 的值.因此，在经过第一次循环之后得出x 等于1f 而y 等于012f f f +=.另外，在经过1n -次循环之后x 等于1n f -而且y 等于n f .当1n >时，用这个迭代方法求出n f 仅仅使用了1n -次加法.因此，这个算法比递归算法需要少得多的计算.
参考文献
[1] 华罗庚. 数学归纳法[M].北京：科学出版社，2002.
[2] 屈婉玲. 离散数学[M].北京：清华大学出版社，2005.
[3] 邓辉文. 离散数学[M].北京：清华大学出版社，2006.
[4] 邵学才. 离散数学[M].北京：清华大学出版社，2006.
[5] 魏献祝. 高等代数[M].上海：华东师范大学出版社，1990.
[6] 霍元极. 高等代数[M].北京：北京师范大学出版社，1990.
[7] 多西. 离散数学：第4版[M].北京：清华大学出版社，2005.
[8] 左孝凌. 离散数学[M].上海：上海科学技术文献出版社，1982.
[9] 约翰索鲍. 离散数学：第5版[M].北京：人民邮电出版社, 2003.
[10]费尔，克朗. 离散数学：双语版[M].北京：清华大学出版社，2005.
[11] Kenneth H.Rosen. 离散数学及其应用：原书第4版[M].北京：机械工业出版社，
2002.
[12] 科尔曼，巴斯比，罗斯. 离散数学结构：第5版翻译版[M].北京：高等教育出版
社，2005.
[13] Susanna. Discrete Mathematics with Applications：第3版[M].北京：高等
教育出版社，2005.
[14] J. R. Monk. Introduction to Set Theory[M].NewYork：McGrawHill，1969.
[15] E. Mendelson. Introduction to Mathematical Logic [M].New York：Van Nostrand
Reinhold， 1964.
《数学归纳法及其应用举例》教案
《数学归纳法及其应用举例》教案 中卫市第一中学 俞清华 教学目标： 1．认知目标：了解数学归纳法的原理，掌握用数学归纳法证题的方法。 2．能力目标：培养学生理解分析、归纳推理和独立实践的能力。 3．情感目标：激发学生的求知欲，增强学生的学习热情，培养学生辩证唯物主义的世界观 和勇于探索的科学精神。 教学重点： 了解数学归纳法的原理及掌握用数学归纳法证题的方法。 教学难点： 数学归纳法原理的了解及递推思想在解题中的体现。 教学过程： 一．创设情境，回顾引入 师：本节课我们学习《数学归纳法及其应用举例》（板书）。首先给大家讲一个故事：从前有 一个员外的儿子学写字，当老师教他写数字的时候，告诉他一、二、三的写法时，员外儿子很高兴，告诉老师他会写数字了。过了不久，员外要写请帖宴请亲朋好友到家里做客，员外儿子自告奋勇地要写请帖。结果早晨开始写，一直到了晚间也没有写完，请问同学们，这是为什么呢？ 生：因为有姓“万”的。 师：对！有姓“万”的。员外儿子万万也没有想到“万”不是一万横，而是这么写的“万”。通过这个故事，你对员外儿子有何评价呢？ 生：（学生的评价主要会有两种，一是员外儿子愚蠢，二是员外儿子还是聪明的。） 师：其实员外儿子观察、归纳、猜想的能力还是很不错的，但遗憾的是他猜错了！在数学 上，我们很多时候是通过观察→归纳→猜想，这种思维过程去发现某些结论，它是一种创造性的思维过程。那么，我们在以前的学习过程中，有没有也像员外儿子那样猜想过某些结论呢？ 生：有。例如等差数列通项公式的推导。 师：很好。我们是由等差数列前几项满足的规律：d a a 011+=，d a a +=12，d a a 213+=，d a a 314+=，……归纳出了它的通项公式的。其实我们推导等差数列通项公式的方法和员外儿子猜想数字写法的方法都是归纳法。那么你能说说什么是归纳法，归纳法有什么特点吗？ 生：由特殊事例得出一般结论的归纳推理方法，通常叫做归纳法。特点：特殊→一般。 师：对。（投影展示有关定义） 像这种由特殊事例得出一般结论的归纳推理方法，通常叫做归纳法。根据推理过程中考察的 对象是涉及事物的一部分还是全部，分为不完全归纳法和完全归纳法。 完全归纳法是一种在研究了事物的所有（有限种）特殊情况后得出一般结论的推理方法，又 叫做枚举法。那么，用完全归纳法得出的结论可靠吗？ 生：（齐答）可靠。 师：用不完全归纳法得出的结论是不是也是可靠的呢？为什么？
浅谈数学归纳法
浅谈数学归纳法 国良 井冈山大学数理学院邮编：343009 指导老师：艳华 [摘要]用数学归纳法证明数学问题时，要注意它的两个步骤缺一不可，第一步是命题递推的基础，第二步是命题递推的依据，也是证明的关键和难点，两个步骤各司其职，互相配合.数学归纳法经历无数数学的潜心研究与科学家们的利用，是数学归纳法得以发展和它为数学问题与科学问题的发现做出了极大的贡献。学好归纳法是科学问题研究的最基础的知识. [关键词]理论依据；数学归纳法；表现形式 1 数学归纳法的萌芽和发展过程 数学归纳法思想萌芽可以说长生于古希腊时代。欧几里德在证明素数有无穷多多个时，使用了反证法，通过反设“假设有有限多个”，使问题变成“有限”的命题，其中证明里隐含着：若有n个素数，就必然存在第n+1个素数，因而自然推出素数有无限多个，这是一种是图用有限处理无限的做法，是人们通过过有限和无限的最初尝试。 欧几里德之后直到16世纪，在意大利数学家莫洛克斯的《算术》一书中明确提出一个“递归推理”原则，并用它证明了1+2+3+…+（2n-1）=2n,对任何自然数n都成立。不过他并没有对这原则做出清晰的表述。 对数学归纳法首次作出明确而清晰阐述的是法国数学家和物理学家帕斯卡，他发现了一种被后来成为“帕斯卡三角形”的数表。他在研究证明有关这个“算术三角形”的一些命题时，最先准确而清晰的指出了证明过程且只需的两个步骤，称之为第一条引理和第二条引理：
第一条引理 该命题对于第一底（即(n=1)成立，这是显然的。 第二条引理 如果该命题对任意底（对任意n ）成立，它必对其下一底（对n+1）也成立。 由此可得，该命题对所有n 值成立。 因此，在数学史上，认为帕斯卡是数学归纳法的创建人，因其所提出的两个引理从本质上讲就是数学归纳法的两个步骤，在他的著作《论算术三角形》中对此作了详尽的论述。 帕斯卡的思想论述十一例子来述归纳法的，而在他的时代还未建立表示一般自然数的符号。直至十七世纪，瑞士数学家J 。伯努利提出表示任意自然熟的符号之后，在他的《猜度术》一书中，才给出并使用了现代形式的数学归纳法。由此，数学归纳法开始得到世人的承认并得到数学界日益广泛的应用。十九世纪，意大利数学家皮亚若建立自然数的公理体系时，提出归纳公理，为数学归纳法奠定了理论基础。即：对于正整数N +的子集M ，如果满足：①1∈M;②若a ∈M ，则a+1∈M ；则M=N +. 2 数学归纳法的表现形式 2.1 第一数学归纳法 原理1：设()P n 是一个与正整数有关的命题，如果 （1）当00()n n n N +=∈时，()P n 成立； （2）假设0(,)n k k n k N +=≥∈时命题成立,由此推得n=k+1时，()P n 也成立； 那么，对一切正整数n 0n ≥,()P n 成立。 证明：反证法.假设该命题不是对于一切正整数都成立.令S 表示使该命题不成立的正整数作成的集合，那么S ≠?，于是由最小数原理，S 中有最小数a ,
各种数学归纳法
1.5 归纳法原理与反归纳法 数学归纳法是中学教学中经常使用的方法．中学教材中的数学归纳法是这样叙述的：如果一个命题与自然数有关，命题对n =1正确；若假设此命题对n －1正确，就能推出命题对n 也正确，则命题对所有自然数都正确．通俗的说法：命题对n =1正确，因而命题对n =2也正确，然后命题对n =3也正确，如此类推，命题对所有自然数都正确．对于中学生来说，这样形象地说明就足够了；但是毕竟自然数是无限的，因而上述描述是不够严格的，有了皮阿罗公理后，我们就能给出归纳法的严格证明． 定理1.19 如果某个命题Ｔ，它的叙述含有自然数，如果命题Ｔ对n =1是正确的，而且假定如果命题Ｔ对n 的正确性就能推出命题Ｔ对n +1也正确，则命题Ｔ对一切自然数都成立．（第一数学归纳法） 证明 设Ｍ是使所讨论的例题Ｔ正确的自然数集合，则 (1) M ∈1． 设M n ∈，则命题Ｔ对n 正确，这时命题对n n '=+1也正确，即 (2) M n ∈' 所以由归纳公理Ｄ，Ｍ含有所有自然数，即命题Ｔ对所有自然数都成立． 下面我们给出一个应用数学归纳法的命题． 例１ 求证 6 ) 12)(1(212 2 2 ++= +++n n n n 证明 (1)当n =1时，有 16 ) 112()11(112 =+?++?= 所以n =1，公式正确． (2)假设当k =n 时，公式正确，即 6 ) 12)(1(212 2 2 ++= +++n n n n 那么当k =n ＋１时，有 =+++++=+++++2 2222222)1()21()1(21n n n n =++++2 ) 1(6 ) 12)(1(n n n n =++++6 ) 1(6)12)(1(2 n n n n =++++6 )] 1(6)12()[1(n n n n =+++6 ) 672)(1(2 n n n =+++6) 32)(2)(1(n n n =+++++6 ) 1)1(2)(1)1)((1(n n n 所以公式对n +1也正确．
数学归纳法及其应用举例1
数学归纳法及其应用举例 【本章学习目标】 人们在研究数量的变化时，常常会遇到有确定变化趋势的无限变化过程，这种无限变化过程就是极限的概念与思想，极限是人们研究许多问题的工具。以刘微的“割圆术”为例，圆内接正n 边形的边数无限增加时，正n 边形的周长P n 无限趋近于圆周长2πR 。这里的是个有限多项的数列，人们可以从这个有限多项的数列来探索无穷数列的变化趋势。不论n 取多么大的整数，n P 都是相应的圆周长的近似值，但是我们可以从这些近似值的精确度的无限提高中（限n 无限增大）找出圆周长的精确值2πR 。随着n 的增加，n P 在变化，这可以认为是量变（即只要n 是有限数，n P 都是圆内接正多边形的周长）；但是我们可以从这些量变中来发现圆周长。一旦得出2πR ，就是质的变化（即不再是正多边形的周长）。这种从有限中认识无限，从近似中认识精确，从量变中认识质变的思想就是极限的思想。 本章重点内容是： （1）数学归纳法及其应用。 （2）研究性课题：杨辉三角。 （3）数列的极限。 （4）函数的极限。 （5）极限的四则运算。 （6）函数的连续性。 本章难点内容是： （1）数学归纳法的原理及其应用。 （2）极限的概念。 【基础知识导引】 1．了解数学推理中的常用方法——数学归纳法。 2．理解数学归纳法的科学性及用数学归纳法来证明与正整数有关命题的步骤。 3．掌握数学归纳法的一些简单应用。 【教材内容全解】 1．归纳法
前面我们在学习等差数列时，通过等差数列的前几项满足的关系式归纳出等差数列的通项公式。再如根据三角形、四边形、五边形、六边形等的内角和归纳出凸n 边形内角和公式。像这样由一系列有限的特殊事例得出一般结论的推理方法，叫做归纳法。 对于归纳法我们可以从以下两个方面来理解。 （1）归纳法可以帮助我们从具体事列中发现事物的一般规律。 （2）根据考察的对象是全部还是部分，归纳法又分完全归纳法与不完全归纳法。显然等差数列通项公式，凸n 边形内角和公式都是通过不完全归纳法得出的，这些结论是正确的。但并不是所有由不完全归纳法得出的结论都是正确的。这是因为不完全归纳只考察了部分情况，结论不具有普遍性。例如课本62P 数列通项公式22)55(+-=n n a n 就是一个典型。 2．数学归纳法 在生活与生产实践中，像等差数列通项公式这样与正整数有关的命题很多。由于正整数有无限多个，因而不可能对所有正整数一一加以验证。如果只对部分正整数加以验证就得出结论，所得结论又不一定正确，要是找到把所得结论递推下去的根据，就可以把结论推广到所有正整数。这就是数学归纳法的基本思想：即先验证使结论 有意义的最小正整数0n ，如果当0n n =时，命题成立，再假设当 ),(*0N k n k k n ∈≥=时，命题成立（这时命是否成立不是确定的），根据这个假设，如能推出当n=k+1时，命题也成立，那么就可以递推出对所有不小于0n 的正整数命题都成立。 由此可知，用数学归纳法证明一个与正整数有关的命题时，要分两个步骤，且两个步骤缺一不可。 第一步递推的基础，缺少第一步，递推就缺乏正确的基础，一方面，第一步再简单，也不能省略。另一方面，第一步只要考察使结论成立的最小正整数就足够了，一般没有必要再多考察几个正整数。 第二步是递推的根据。仅有这一步而没有第一步，就失去了递推的基础。例如，假设n=k 时，等式 成立，就是。那么， 。这就是说，如果n=k 时等式成立， 那么n=k+1时等式也成立。但仅根据这一步不能得出等式对于任何n ∈N*都成立。因为当n=1时，上式左边=2，右边31112=++=，左边≠右边。这说明了缺少第一步这个基础，第二步的递推也就没有意义了。只有把第一步的结论与第二步的结论结合在一起，才能得出普遍性结论。因此，完成一、二两点后，还要做一个小结。 在证明传递性时，应注意： （1）证n=k+1成立时，必须用n=k 成立的假设，否则就不是数学归纳法。应当指出，n=k 成立是假设的，这一步是证明传递性，正确性由第一步可以保证，有了递推这一步，联系第一步的结论（命题对0n n =成立），就可以知道命题对10+n 也成立，进而再由第二步可知1)1(0++=n n ，即20+=n n 也成立。这样递推下去，就可以知道命题对所有不小于0n 的正整数都成立。 （2）证n=k+1时，可先列出n=k+1成立的数学式子，作为证明的目标。可以作为条件加以运用的有n=k 成立的假设，已知的定义、公式、定理等，不能直接将n=k+1代入命题。 3．这一节课本中共安排了五个例题，例1～例3是用数学归纳法证明等式。其步骤是先证明当0n n =（这里10=n ）时等式成立。再假设当n=k 时等式成立，利用这一条件及已知的定义、公式、定理证明当n=k+1时等式也成立。注意n=k+1时的等式是待证明的，不能不利用假设。例如：求证：。
浅谈数学归纳法在高考中的应用
1、数学归纳法的理论基础 数学归纳法，人类天才的思维、巧妙的方法、精致的工具，解决无限的问题。它体现的是利用有限解决无限问题的思想，这一思想凝结了数学家们无限的想象力和创造力，这无疑形成了数学证明中一道绚丽多彩的风景线。它的巧妙让人回味无穷，这一思想的发现为后来数学的发展开辟了道路，如用有限维空间代替无限维空间（多项式逼近连续函数）用有限过程代替无限过程（积分和无穷级数用有限项和答题，导数用差分代替）。 1.1数学归纳法的发展历史 自古以来，人们就会想到问题的推广，由特殊到一般、由有限到无限，可人类对无限的把握不顺利。在对无穷思考的过程中，古希腊出现了许多悖论，如芝诺悖论，在数列中为了确保结论的正确，则必须考虑无限。还有生活中一些现象，如烽火的传递，鞭炮的燃放等，触动了人类的思想。 安提丰用圆周内接正多边形无穷地逼近圆的方法解决化圆为方；刘徽、祖冲之用圆内接正多边形去无穷地逼迫圆，无穷的问题层出不穷，后来古希腊欧几里得对命题“素数的个数是无穷的”的证明，通过了有限去实现无限，体现了数学归纳法递推思想。但要形成数学归纳法中明确的递推，清晰的步骤确是一件不容易的事，作为自觉运用进行数学证明却是近代的事。 伊本海塞姆（10世纪末）、凯拉吉（11世纪上叶）、伊本穆思依姆（12世纪末）、伊本班纳（13世纪末）等都使用了归纳推理，这表明数学归纳法使用较普遍，尤其是凯拉吉利用数学归纳法证明 22 333 (1)124n n n +++??????+= 这是数学家对数学归纳法的最早证明。 接着,法国数学家莱维.本.热尔松(13世纪末)用"逐步的无限递进"，即归纳推理证明有关整数命题和排列组合命题。他比伊斯兰数学家更清楚地体现数学归纳法证明的基础，递进归纳两个步骤。 到16世纪中叶，意大利数学家毛罗利科对与全体和全体自然数有关的命题的证明作了深入的考察在1575年，毛罗利科证明了 21n n a a n ++= 其中1231,2k a k =+++?????? =?????? 他利用了逐步推理铸就了“递归推理”的思路，成为了较早找到数学归纳中“递 归推理”的数学家，为无限的把握提供了思维。 17世纪法国数学家帕斯卡为数学归纳法的发明作了巨大贡献，他首先明确而清晰地阐述数学归纳法的运用程序，并完整地使用数学归纳法，证明了他所发
高中数学《数学归纳法及其应用举例》教学设计附反思
课题：数学归纳法及其应用举例 【教学目标】 知识与技能： 1. 了解由有限多个特殊事例得出的一般结论不一定正确，使学生深入认识归纳法, 理解数学归纳法的原理与实质; 2. 掌握数学归纳法证题的两个步骤；初步会用“数学归纳法”证明简单的与自然数有关的命题(如恒等式等)． 3. 培养学生观察、分析、论证的能力, 进一步发展学生的抽象思维能力和创新能力，让学生经历数学归纳法原理的构建过程, 体会类比的数学思想．过程与方法: 1.努力创设和谐融洽的课堂情境，使学生处于积极思考、大胆质疑氛围，提高学生学习的兴趣和课堂效率．让学生体验知识的构建过程, 体会源于生活的数学思想; 2. 通过对数学归纳法的学习、应用，逐步体验观察、归纳、猜想、论证的过程，培养学生由特殊到一般的思维方式和严格规范的论证意识，并初步掌握论证方法; 3. 让学生经历发现问题、提出问题、分析问题、解决问题的过程，培养学生创新能力. 情感、态度、价值观: 1. 通过对数学归纳法原理的探究，培养学生严谨的、实事求是的科学态度和不怕困难，勇于探索的精神； 2. 让学生通过对数学归纳法原理和本质的理解，感受数学内在美的震撼力，从而使学生喜欢数学,激发学生的学习热情，使学生初步形成做数学的意识和科学精神； 3. 学生通过置疑与探究，培养学生独立的人格与敢于创新的精神； 4. 持续增进师生互信，生生互助，共创教学相长的教与学的氛围和习惯. 【教学重点】 归纳法意义的认识和数学归纳法产生过程的分析，初步理解数学归纳法的原理并能简单应用. 【教学难点】 数学归纳法中递推思想的理解,初步明确用数学归纳法证明命题的两个步骤. 【教学方法】师生互动讨论、共同探究的方法 【教学手段】多媒体辅助课堂教学 【教学过程】 一、创设情境，启动思维 情境一、财主儿子学写字的笑话、“小明弟兄三个，大哥叫大毛……”的脑筋急转弯等； 教师总结：财主的儿子很傻很天真，但他懂一样思想方法，是什么？以上都是由特殊情况归纳出一般情况的方法---归纳法，这就是今天的课题. 人们通常
1.5 归纳法原理与反归纳法
---------------------------------------------------------------最新资料推荐------------------------------------------------------ 1.5 归纳法原理与反归纳法 1.5 归纳法原理与反归纳法数学归纳法是中学教学中经常使用的方法．中学教材中的数学归纳法是这样叙述的： 如果一个命题与自然数有关，命题对 n=1 正确；若假设此命题对 n－1 正确，就能推出命题对n 也正确，则命题对所有自然数都正确．通俗的说法： 命题对 n=1 正确，因而命题对 n=2 也正确，然后命题对 n=3 也正确，如此类推，命题对所有自然数都正确．对于中学生来说，这样形象地说明就足够了；但是毕竟自然数是无限的，因而上述描述是不够严格的，有了皮阿罗公理后，我们就能给出归纳法的严格证明．定理 1.19 如果某个命题Ｔ，它的叙述含有自然数，如果命题Ｔ对 n=1 是正确的，而且假定如果命题Ｔ对 n 的正确性就能推出命题Ｔ对 n+1 也正确，则命题Ｔ对一切自然数都成立．（第一数学归纳法）证明设Ｍ是使所讨论的例题Ｔ正确的自然数集合，则 M1．设Mn ，则命题Ｔ对 n 正确，这时命题对(2) Mn 所以由归纳公理Ｄ，Ｍ含有所有自然数，即命题Ｔ对所有自然数都成立．下面我们给出一个应用数学归纳法的命题．例１求证(1) nn=+1也正确，即6) 证明 (1)当 n=1 时，有 16) 112 () 11 (112=+++= 所以 n=1，公式正确． (2)假设当 k=n 时，公式正确，即那么当 k=n＋１时，有 1 / 9
高中数学《数学归纳法及应用举例》说课稿
《数学归纳法及应用举例》第一课说课方案 一、说教材 （一）教材分析 本课是数学归纳法的第一节课。前面学生已经通过数列一章内容和其它相关内容的学习，初步掌握了 由有限多个特殊事例得出一般结论的推理方法，即不完全归纳法。不完全归纳法它是研究数学问题，猜想或发现数学规律的重要手段。但是，由有限多个特殊事例得出的结论不一定正确，这种推理方法不能作为 一种论证方法。因此，在不完全归纳法的基础上，必须进一步学习严谨的科学的论证方法─数学归纳法。 数学归纳法安排在数列之后极限之前，是促进学生从有限思维发展到无限思维的一个重要环节。并且，本 节内容是培养学生严密的推理能力、训练学生的抽象思维能力、体验数学内在美的好素材。 （二）教学目标 学生通过数列等相关知识的学习。已基本掌握了不完全归纳法，已经有一定的观察、归纳、猜想能力。通过近几年教学方法的改革和素质教育的实施，学生已基本习惯于对已给问题的主动探究，但主动提出问 题和置疑的习惯还未形成。能主动提出问题和敢于置疑是学生具有独立人格和创新能力的重要标志。如何 让学生主动置疑和提出问题？本课也想在这方面作一些尝试。 根据教学内容特点和教学大纲、根据学生以上实际、根据学生终身发展需要而制订以下教学目标。 1.知识目标 （1）了解由有限多个特殊事例得出的一般结论不一定正确。 （2）初步理解数学归纳法原理。 （3）理解和记住用数学归纳法证明数学命题的两个步骤。 （4）初步会用数学归纳法证明一些简单的与正整数有关的恒等式。 2.能力目标 （1）通过对数学归纳法的学习、应用，培养学生观察、归纳、猜想、分析能力和严密的逻辑推理能力。 （2）让学生经历发现问题、提出问题、分析问题、解决问题的过程，培养学生的创新能力。 3.情感目标 （1）通过对数学归纳法原理的探究，培养学生严谨的、实事求是的科学态度和不怕困难，勇于探索的精神。 （2）让学生通过对数学归纳法原理的理解，感受数学内在美的振憾力，从而使学生喜欢数学。 （3）学生通过置疑与探究，培养学生独立的人格与敢于创新精神。 （三）教学重难点 根据教学大纲要求、本节课内容特点和学生现有知识水平，确定如下教学重难点： 1.重点 （1）初步理解数学归纳法的原理。 （2）明确用数学归纳法证明命题的两个步骤。 （3）初步会用数学归纳法证明简单的与正整数数学恒等式。 2.难点 （1）对数学归纳法原理的理解，即理解数学归纳法证题的严密性与有效性。 （2）假设的利用，即如何利用假设证明当n=k+1时结论正确。 二、说教法 本课采用交往式的教学方法。交往教学法的特点是：在教师的组织启发下，师生之间、学生之间共同 探讨，平等交流;既强调独立思考，又提倡团结合作;既重视教师的组织引导，又强调学生的主体性、主动 性、平等性、开放性、合作性。这种教学方法的优点是学生心态开放，主体性和主动性凸现，独立的个性 得到张扬，因而创造性得到解放。 三、说学法 本课以问题为中心，以解决问题为主线展开，学生主要采用“探究式学习法”进行学习。本课学生的 学习主要采用下面的模式进行： 观察情景提出问题分析问题猜想与置疑（结论或解决问题的途径） 论证应用。 探究学习法的好处是学生主动参与知识的发生、发展过程。学生在探究问题过程中学习，在探究问题 的过程中激发学生的好奇心和创新精神;在探究过程中学习科学研究的方法;在探究过程中形成坚韧不拔
浅谈数学归纳法及其在中学数学中的应用2
目录 1、数学归纳法---------------------------------------------------------- 3 1.1 归纳法定义-------------------------------------------------------- 3 1.2 数学归纳法体现的数学思想----------------------------------------- 4 1.2.1 从特殊到一般------------------------------------------------ 4 1.2.2 递推思想---------------------------------------------------- 4 2、数学归纳法在中学数学中的应用技巧------------------------------------- 5 2.1 强调------------------------------------------------------------- 5 2.1.1 两条缺一不可------------------------------------------------ 5 2.2 技巧------------------------------------------------------------- 5 2.2.1 认真用好归纳假设-------------------------------------------- 5 2.2.2 学会从头看起------------------------------------------------ 6 2.2.3 在起点上下功夫---------------------------------------------- 7 2.2.4 正确选取起点和过渡------------------------------------------ 8 2.2.5 选取适当的归纳假设形式-------------------------------------- 9 3、数学归纳法在中学数学中的应用 ---------------------------------------- 9 3.1 证明有关自然数的等式--------------------------------------------- 9 3.2 证明有关自然数的不等式------------------------------------------ 11 3.3 证明不等式------------------------------------------------------ 11 3.4 在函数迭代中的应用---------------------------------------------- 12 3.5 在几何中的应用-------------------------------------------------- 14 3.6 在排列、组合中的应用-------------------------------------------- 16 3.7 在数列中的应用-------------------------------------------------- 16 3.8 有关整除的问题-------------------------------------------------- 17
数学归纳法的应用
数学归纳法的应用 姓名 甘国优 指导教师 赵慧炜 中文摘要：数学归纳法是数学中一种非常普遍的证题的方法，其应用极为广泛．本次主要简述了数学归纳法的简略步骤：观察（探索）﹑归纳﹑猜想﹑证明于一体的数学思想，体现出数学归纳法的证题思路．并归纳总结了数学归纳法解决代数恒等式﹑几何等方面的一些简单应用问题的方法，对应用中常见的误区加以剖析，以及介绍一些证题方法技巧，有助于提高对数学归纳法的应用能力． 关键词：数学归纳法；步骤;证明方法． Abstract: Mathematical induction is a common evidence method in mathematics, it is have very broad application. In this paper, author research into the step of the Mathematical induction , it includes summariz ，evidence and guess embody the idea of the evidence of mathematical induction. Also at here ,we summariz the method of the mathematical induction application in solve algebra identities , geometric ,order and portfolio ,and so on .also analyze the common errors on application and into duct skill of the proof ,proof of skills introduced. It is help to increased the level of the Mathematical induction’s application ． Key words ：Mathematical induction; Steps ; Proof. 引言 演绎和归纳是人在思维过程中两个完全相反的过程.同时又是数学思维中两种基本的方法.数学归纳法是一种重要的数学证明方法，他有着其他方法所不能代替的作用，也是证明与自然数有关的数学命题的一种完全归纳法.我们在学习运用数学归纳法应具备两个条件：①当1n =时，这个命题为正确的（奠基），②当n k =时，这个命题也为正确的．推出当+1n k =时，这个命题也为正确的（递推）．通过“递推”链接，实现从特殊到一般的转化，抽象的进行数学归纳.首先
数学论文 浅谈数学归纳法的应用
浅谈数学归纳法的应用 数学归纳法是证明与自然数有关的命题的一种方法，应用广泛．在最近几年的高考试卷中体现的特别明显，以下通过几道高考试题来谈一谈数学归纳法的应用。 一、用数学归纳法证明整除问题 用数学归纳法证明整除问题时，由到时，首先要从要证的式子中拼凑出假设成立的式子，然后证明剩余的式子也能被某式（数）整除，这是数学归纳法证明问题的一大技巧。 例1、是否存在正整数m ，使得f （n ）=（2n +7）·3n +9对任意自然数n 都能被m 整除?若存在，求出最大的m 值，并证明你的结论;若不存在，请说明理由. 证明：解：由f （n ）=（2n +7）·3n +9，得f （1）=36， f （2）=3×36， f （3）=10×36， f （4）=34×36，由此猜想m =36. 下面用数学归纳法证明： （1）当n =1时，显然成立. （2）假设n =k 时， f （k ）能被36整除，即f （k ）=（2k +7）·3k +9能被36整除;当n =k +1时，［2（k +1）+7］·3k +1+9=3［（2k +7）·3k +9］+18（3k --1－1）， 由于3k -1－1是2的倍数，故18（3k － 1－1）能被36整除.这就是说，当n =k +1时，f （n ）也能被36整除. 由（1）（2）可知对一切正整数n 都有f （n ）=（2n +7）·3n +9能被36整除，m 的最大值为36. 二、用数学归纳法证明恒等式问题 对于证明恒等的问题，在由证等式也成立时，应及时把结论和推导过程对比，也就是我们通常所说的两边凑的方法，以减小计算的复杂程度，从而发现所要证明的式子，使问题的证明有目的性． 例2、是否存在常数c b a ,,，使得等式)(12 )1()1(32212222c bn an n n n n +++=+?++?+?对一切自然数n 成立？并证明你的结论． 解：假设存在c b a ,,，使得题设的等式成立，则当时3,2,1=n 也成立，代入得 ???? ?????++=++=++=c b a c b a c b a 3970)24(2122)(614 解得10,11 ,3===c b a ，于是对3,2,1=n ，下面等式成立： )10113(12)1()1(32212222+++= +?++?+?n n n n n n 令222)1(3221+?++?+?=n n S n 假设k n =时上式成立，即)10113(12 )1(2+++= k k k k S k 那么21)2)(1(+++=+k k S S k k 22)2)(1()10113(12 )1(++++++=k k k k k k
数学归纳法原理：【第二归纳法】【跳跃归纳法】【反向归纳法】
数学归纳法原理(六种)：【第二归纳法】【跳跃归纳法】【反向归纳法】 一行骨牌，如果都充分地靠近在一起（即留有适当间隔），那么只要推倒第一个，这一行骨牌都会倒塌；竖立的梯子，已知第一级属于可到达的范围，并且任何一级都能到达次一级，那么我们就可以确信能到达梯子的任何一级；一串鞭炮一经点燃，就会炸个不停，直到炸完为止；……，日常生活中这样的事例还多着呢！ 数学归纳法原理设P(n)是与自然数n有关的命题．若 (I)命题P(1)成立； (Ⅱ)对所有的自然数k，若P(k)成立，推得P(k+1)也成立. 由（I）、(Ⅱ)可知命题P(n)对一切自然数n成立． 我们将在“最小数原理”一章中介绍它的证明， 运用数学归纳法原理证题的方法，是中学数学中的一个重要的方法，它是一种递推的方法，它与归纳法有着本质的不同．由一系列有限的特殊事例得出一般结论的推理方法，通常叫做归纳法，用归纳法可以帮助我们从具体事例中发现一般规律，但是，仅根据一系列有限的特殊事例得出的一般结论的真假性还不能肯定，这就需要采用数学归纳法证明它的正确性． 一个与自然数n有关的命题P(n)，常常可以用数学归纳法予以证明，证明的步骤为：(I)验证当n取第1个值no时，命题P(no)成立，这一步称为初始验证步． (Ⅱ)假设当n=k(k∈N，后≥no)时命题P(k)成立，由此推得命题P(k+1)成立．这一步称为归纳论证步． (Ⅲ)下结论，根据(I)、(Ⅱ)或由数学归纳法原理断定，对任何自然数(n≥no)命题 P(n)成立．这一步称为归纳断言步， 为了运用好数学归纳法原理，下面从有关注意事项与技巧及运用递推思想解题等几个方面作点介绍． 运用数学归纳法证题时应注意的事项与技巧三个步骤缺一不可 第一步是递推的基础，第二步是递推的依据，第三步是递推的过程与结论．三步缺一不可．数学归纳法的其他几种形式还有：第二数学归纳法；跳跃数学归纳法；倒推数学归纳法（反向归纳法）；分段数学归纳法二元有限数学归纳法；双向数学归纳法；跷跷板数学归纳法；同步数学归纳法等。 1.5归纳法原理与反归纳法 数学归纳法是中学教学中经常使用的方法．中学教材中的数学归纳法是这样叙述的：如果一个命题与自然数有关，命题对n=1正确；若假设此命题对n－1正确，就能推出命题对n也正确，则命题对所有自然数都正确．通俗的说法：命题对n=1正确，因而命题对n=2也正确，然后命题对n=3也正确，如此类推，命题对所有自然数都正确．对于中学生来说，这样形象地说明就足够了；但是毕竟自然数是无限的，因而
数学归纳法在离散数学中的应用
数学归纳法在离散数学中的应用 在由一系列有限的特殊事例得出一般性结论的推理方法称为归纳法。而 数学归纳法则是用于证明与自然数n 有关的结论的归纳法：如果我们能够证明当n=1时结论是成立的，而且我们能用相同的方法由n=1命题成立证得n=2命题也成立；由n=2命题成立证得n=3成立；由n=3命题成立证得n=4成立…而且这个过程显然可以无穷进行下去。则我们就断言对于所有自然数n 命题都是成立的。数学归纳法的一般形式为，关键是归纳： 初始步）：先证n ＝1时，结论成立； 归纳步)：再证若假设对自然数n ＝k 结论成立（或者对所有小于等于n 的 自然数k 结论都成立），则对下一个自然数n ＝k+1结论也成立； 结论）： 根据初始步和归纳步的证明得出结论对所有自然数都成立。 当结论与多个自然数有关时这样一类题目的时候，要注意的一点就是对所要进行归纳的自然数的选择。 例1、对群
数学归纳法几种常见方式及其应用中存在的问题论文
数学归纳法几种常见方式及其应用中存在的问题 摘要 在处理数学问题时，经常涉及与任意自然数有关的一些命题，这些命题实质上是由无限个n取具体整数时得到的无限个命题组成的，我们往往不能逐一验证，这时，数学归纳法就是我们最常应用的一个有效的推理方法，为什么我们能够相信数学归纳法的证明呢？因为数学归纳法实质上是一种演绎推理法，华罗庚老先生是这样解释数学归纳法原理的：“我们采用形式上的讲法，也就是：有一批编了号码的数学命题，我们能够证明第1号命题是正确的；如果我们能够证明在第K 号命题正确的时候，第K+1号命题也是正确的，那么，这一批命题就全部正确.”其实，数学归纳法的正确性在我们学到的自然数的公理系统已经得到说明，他是与皮亚诺公理等价的一个本原性命题. 关键字数学归纳法常见方式及问题无限有限 数学归纳法（Mathematical Induction，通常简称为MI）是一种数学证明方法，通常被用于证明某个给定命题在整个（或者局部）自然数范围内成立。是用来研究与正整数有关的数学问题，在高中数学中常用来证明等式（不等式）成立和数列通项公式成立。 数学归纳法一般分为以下几种常见的方式： （一）第一数学归纳法： 一般地，证明一个与自然数n有关的命题P(n），有如下步骤 （1）证明当n取第一个值n0时命题成立。n0对于一般数列取值为0或1，但也有特殊情况； （2）假设当n=k（k≥n0，k为自然数）时命题成立，证明当n=k+1时命题也成立。 综合（1）（2），对一切自然数n（≥n0），命题P(n）都成立。 （二）第二数学归纳法： 对于某个与自然数有关的命题P(n）， （1）验证n=n0时P(n）成立； （2）假设n0≤n<=k时P(n）成立，并在此基础上，推出P(k+1）成立。 综合（1）（2），对一切自然数n（≥n0），命题P(n）都成立。 （三）倒推归纳法（反向归纳法）： （1）验证对于无穷多个自然数n命题P(n）成立， （2）假设P(k+1）（k≥n0）成立，并在此基础上，推出P(k）成立， 综合（1）（2），对一切自然数n（≥n0），命题P(n）都成立。 （四）螺旋式归纳法
利用数学归纳法解题举例
利用数学归纳法解题举例 归纳是一种有特殊事例导出一般原理的思维方法。归纳推理分完全归纳推理与不完全归纳推理两种。不完全归纳推理只根据一类事物中的部分对象具有的共同性质，推断该类事物全体都具有的性质，这种推理方法，在数学推理论证中是不允许的。完全归纳推理是在考察了一类事物的全部对象后归纳得出结论来。 数学归纳法是用来证明某些与自然数有关的数学命题的一种推理方法，在解数学题中有着广泛的应用。它是一个递推的数学论证方法，论证的第一步是证明命题在n＝1(或n )时成立，这是递推的基础；第二步是假设在n＝k时命题成立， 再证明n＝k＋1时命题也成立，这是无限递推下去的理论依据，它判断命题的正确性能否由特殊推广到一般，实际上它使命题的正确性突破了有限，达到无限。这两个步骤密切相关，缺一不可，完成了这两步，就可以断定“对任何自然数（或 n≥n 且n∈N）结论都正确”。由这两步可以看出，数学归纳法是由递推实现归纳0 的，属于完全归纳。 运用数学归纳法证明问题时，关键是n＝k＋1时命题成立的推证，此步证明要具有目标意识，注意与最终要达到的解题目标进行分析比较，以此确定和调控解题的方向，使差异逐步减小，最终实现目标完成解题。 运用数学归纳法，可以证明下列问题：与自然数n有关的恒等式、代数不等式、三角不等式、数列问题、几何问题、整除性问题等等。 一、运用数学归纳法证明整除性问题 例1.当n∈N,求证:11n+1+122n-1能被133整除。 证明:(1)当n=1时，111+1+1212×1-1=133能被133整除。命题成立。 (2)假设n=k时，命题成立，即11k+1+122k-1能被133整除，当n=k+1时，
浅谈数学归纳法
浅谈数学归纳法 陈国良 井冈山大学数理学院江西吉安邮编：343009 指导老师：曹艳华 [摘要]用数学归纳法证明数学问题时，要注意它的两个步骤缺一不可，第一步是命题递推的基础，第二步是命题递推的依据，也是证明的关键和难点，两个步骤各司其职，互相配合.数学归纳法经历无数数学的潜心研究与科学家们的利用，是数学归纳法得以发展和它为数学问题与科学问题的发现做出了极大的贡献。学好归纳法是科学问题研究的最基础的知识. [关键词]理论依据；数学归纳法；表现形式 1 数学归纳法的萌芽和发展过程 数学归纳法思想萌芽可以说长生于古希腊时代。欧几里德在证明素数有无穷多多个时，使用了反证法，通过反设“假设有有限多个”，使问题变成“有限”的命题，其中证明里隐含着：若有n个素数，就必然存在第n+1个素数，因而自然推出素数有无限多个，这是一种是图用有限处理无限的做法，是人们通过过有限和无限的最初尝试。 欧几里德之后直到16世纪，在意大利数学家莫洛克斯的《算术》一书中明确提出一个“递归推理”原则，并用它证明了1+2+3+…+（2n-1）=2n,对任何自然数n都成立。不过他并没有对这原则做出清晰的表述。 对数学归纳法首次作出明确而清晰阐述的是法国数学家和物理学家帕斯卡，他发现了一种被后来成为“帕斯卡三角形”的数表。他在研究证明有关这个“算术三角形”的一些命题时，最先准确而清晰的指出了证明过程且只需的两个步骤，称之为第一条引理和第二条引理： 第一条引理该命题对于第一底（即(n=1)成立，这是显然的。 第二条引理如果该命题对任意底（对任意n）成立，它必对其下一底（对n+1）也成立。 由此可得，该命题对所有n值成立。 因此，在数学史上，认为帕斯卡是数学归纳法的创建人，因其所提出的两个引理从本质上讲就是数学归纳法的两个步骤，在他的著作《论算术三角形》中对此作了详尽的论述。 帕斯卡的思想论述十一例子来陈述归纳法的，而在他的时代还未建立表示一般自然数的符号。直至十七世纪，瑞士数学家J。伯努利提出表示任意自然熟的符号之后，在他的《猜度术》一书中，才给出并使用了现代形式的数学归纳法。由此，
数学归纳法教案(新)
教材背景： 归纳是一种由特殊事例导出一般规律的思维方法．归纳推理分完全归纳推理与不完全归纳推理两种．不完全归纳推理只根据一类事物中的部分对象具有的共同性质，推断该类事物全体都具有的性质，这种推理方法，在数学推理论证中是不允许的．完全归纳推理是在考察了一类事物的全部对象后归纳得出结论来．数学归纳法是用来证明某些与正整数n有关的数学命题的一种推理方法，在数学问题的解决中有着广泛的应用． 教学课题：数学归纳法 教材分析： “数学归纳法”既是高中代数中的一个重点和难点容，也是一种重要的数学方法。它贯通了高中代数的几大知识点：不等式，数列，三角函数……在教学过程中，教师应着力解决的容是：使学生理解数学归纳法的实质，掌握数学归纳法的证题步骤（特别要注意递推步骤中归纳假设的运用和恒等变换的运用）。只有真正了解了数学归纳法的实质，掌握了证题步骤，学生才能信之不疑，才能用它灵活证明相关问题。本节课是数学归纳法的第一节课，有两大难点：使学生理解数学归纳法证题的有效性；递推步骤中归纳假设的利用。不突破以上难点，学生往往会怀疑数学归纳法的可靠性，或者只是形式上的模仿而不知其所以然。这会对以后的学习造成极大的阻碍。根据本节课的教学容和学生实际水平，本节课采用“引导发现法”和“讲练结合法”。通过课件的动画模拟展示，引发和开启学生的探究热情，通过“师生”和“生生”的交流合作，掌握概念的深层实质。 教学目标 1、知识和技能目标 (1)了解数学推理的常用方法（归纳法） (2)了解数学归纳法的原理及使用围。 (3)初步掌握数学归纳法证题的两个步骤和一个结论。 (4)会用数学归纳法证明一些简单的等式问题。 2、过程与方法目标 通过对归纳法的复习，说明不完全归纳法的弊端，通过多米诺骨牌实验引出数学归纳法的原理，使学生理解理论与实际的辨证关系。在学习中培养学生探索发现问题、提出问题的意识，解决问题和数学交流的能力,学会用总结、归纳、演绎类比探求新知识。
- 数学归纳法及应用举例2
- 数学归纳法及其应用举例
- 数学归纳法及应用举例
- 数学归纳法及其应用
- 数学归纳法及应用举例
- 数学归纳法课件.ppt
- 数学归纳法及其应用举例
- 07数学归纳法应用举例
- 数学归纳法及其应用举例中小学PPT教学课件
- 数学归纳法及其应用举例 ppt课件
- 北师大版数学高二-选修4试题 数学归纳法应用举例
- 《数学归纳法及其应用举例》教案
- 数学归纳法应用举例课件人教B版选修
- 21数学归纳法及其应用举例
- 学年高中数学数学归纳法与贝努利不等式数学归纳法应用举例导学案新人教B版选修
- 高中数学《数学归纳法及其应用举例》教学设计附反思
- 数学归纳法应用举例-课件
- 数学归纳法应用举例 课件 3PPT教学课件
- 《数学归纳法及其应用举例》
- 高中数学《数学归纳法及应用举例》说课稿