如何证明贪心算法
这里主要是介绍一种证明贪心算法是最优的一种方法：Exchange Argument （不知道应该怎么翻译到中文，交换参数？感觉听起来挺别扭的，不像是一个方法的名字~o(╯□╰)o）
Exchange Argument的主要的思想也就是先假设存在一个最优的算法和我们的贪心算法最接近，然后通过交换两个算法里的一个步骤(或元素)，得到一个新的最优的算法，同时这个算法比前一个最优算法更接近于我们的贪心算法，从而得到矛盾，原命题成立。
下面来看一个更为formal的解释：
步骤：
Step0: 给出贪心算法A的描述
Step1: 假设O是和A最相似(假设O和A的前k个步骤都相同，第k+1个开始不同，通常这个临界的元素最重要)的最优算法
Step2: [Key] 修改算法O(用Exchange Argument，交换A和O中的一个元素)，得到新的算法O’Step3: 证明O’ 是feasible的，也就是O’是对的
Step4: 证明O’至少和O一样，即O’也是最优的
Step5: 得到矛盾，因为O’ 比O 更和A 相似。
证毕。
当然上面的步骤还有一个变种，如下：
Step0: 给出贪心算法A的描述
Step1: 假设O是一个最优算法（随便选，arbitrary）
Step2: 找出O和A中的一个不同。（当然这里面的不同可以是一个元素在O不再A，或者是一个pair 的顺序在A的和在O的不一样。这个要根据具体题目）
Step3：Exchange这个不同的东西，然后argue现在得到的算法O' 不必O差。
Step4: Argue 这样的不同一共有Polynomial个，然后我exchange Polynomial次就可以消除所有的不同，同时保证了算法的质量不比O差。这也就是说A 是as good as 一个O的。因为O是arbitrary 选的，所以A是optimal的。
证毕
下面给几个例子：
例Maximum Cardinality Disjoint Interval Problem
问题描述：给一些时间片段集合T={（a1，b1）（a2，b2），。。。，（an，bn）}，找出一个元素个数最多的子集S，子集中的每个元素的时间片段没有交叉。
Greedy Algorithm: 每次都选所有interval 中bi最小的那个，把（ai，bi）加入S，然后把（ai，bi）在T中删除，同时把T中所有和（ai，bi）有交叉的interval删除，然后再在T中找最小的bj，循环上面的操作，直到没有可以在添加的。
证明上面说的Greedy Algorithm是最优的。
下面就用第一个证明的步骤来证。
我们的Greedy Algorithm记为A，假设A不是最优的，那么就一定存在一个O，O是和A最相近的一个最优的算法，最相近是指和O和A的前K-1个选择都相同，第K个是不同的。
假设对于A，A第k个选择的是（ai，bi）；而O第K个选择的是（aj，bj）。从A的定义我们可以直到，bi<=bj。
现在我们构造一个O'，O' = O-（aj，bj）+（ai，bi）。
1）很显然，O'是这个问题的一个解，也就是说O'中的intervals没有重叠的。
在O'中，（ai，bi）前的intervals和A中的一样，所以前一部分没有重叠。在（ai，bi）后的intervals 和O中的一样，所以也没有重叠，同时bi<=bj，所以（ai，bi）也不会和它相邻的重叠，所以O'中的所有intervals都没有重叠。
2）O'是一个最优解，因为他的intervals的个数和O一样。
综上，我们找到了一个最优解O'，它和A具有的共同的intervals有K个，这和我们前提假设最多有k-1个相矛盾，所以，A是最优的。证毕。
例Scheduling with Deadline
问题描述：有一系列的tasks{a1，a2，。。。，an}，每个task需要在cpu上跑{p1，p2，。。。，pn}个units的时间，cpu是非抢占式的，也就是task一旦获得cpu，就运行直到他完成，{c1，c2，。。。，cn}是每个task的完成时间，我们现在要minimize的就是（c1+c2+。。。+cn）/n。所有的task一起release。
Greedy Algorithm：每次选运行时间最小的那个task运行。
证明上面说的Greedy Algorithm是最优的。
同样还是用第一个证明的步骤来证。
假设A不是最优的，那么一定存在一个最优的O，和A最接近，他们选择的前k-1个task是相同的。
如下：
No.123。。。k。。。。。。。。。
A 。。。。。。。。。。。ai。。aj 。。。。。
O 。。。。。。。。。。。aj。。。。ai 。。。
根据A的定义，我们知道，pi <= pj的。
现在我们就来构造O'，当然，O'就是把O中的ai和aj两个元素交换一下，即
No.123。。。k。。。。。t。。。
A 。。。。。。。。。。。ai。。aj 。。。。。
O 。。。。。。。。。。。aj。。。。ai 。。。
O' 。。。。。。。。。。。ai。。。。aj 。。。
对于整个的完成时间，我们可以给出计算公式的，假设b1，b2，。。。，bn是一个调度序列（bi是task 的index，也就是{bi}是所有task的index的一个permutation），即task执行顺序是
a_{bi},a_{b2}, ..., a_{bn}。举个例子如果只有5个task，a1,a2,a3,a4,a5。{bi} = {2,1, 3, 5, 4},那也就是task的执行序列为a2,a1,a3,a5,a4。(博客里面不能打数学公式就是不爽啊~)
还是用上面的5个例子算了，对于a2,a1,a3,a5,a4，我们知道总时间其实是5个a2的时间，即p2，4个a1的时间，即p1，依次类推，所以总时间是5*p2+4*p1+3*p3+2*p5+p4。
好，有了上面的计算总时间的概念，下面就来分别计算一下O和O'的总时间，其实我们需要比较它们谁大谁小，通常只要比较一下他们的差就行了，即Time(O)-Time(O')。同时很显然，他们的差只是由aj和ai引起的，其他的并没有改变。我们知道在O中，aj是第k个选的，ai是第t个选的，而在O'中，ai是第k个选的，aj是第t个选的，所以Time(O)-Time(O') = (n-k+1)*pj + (n-t+1)*pi - (n-k+1)*pi - (n-t+1)*pj = k*(pj-pi) - t*(pj-pi) = (pi-pj)*(k-t)>=0,即我们得到Time(O) >= Time(O'),这也就是说我们找到了一个O'，他是最优的，同时O'和A有K个common element，所以得出矛盾。证毕。
例Kruskal Algorithm for Minimum Spanning Tree（最小生成树）
问题描述：对于边集合E，先按每个边的cost排序，从小到大，然后按如下方法构造一个MST，每次选cost最小的那个边，添加进我们的MST，如果一个边使我们现有的MST出现环路，则把这条边舍弃，然后重复上面的操作。（感觉现在表达越来越搓了，没看明白怎么回事的童鞋看这里
吧 https://www.sodocs.net/doc/574560588.html,/wiki/Kruskal's_algorithm）
下面我们就用第二种证明方法来证明Kruskal Algorithm算法是最优的。
假设我们的graph是G(V,E)，有一个optimal的算法O，它生成的MST是T1，Kruskal生成的树是
T2，这样，因为T2！=T1（如果相等我们的Kruskal就最优了，就不用证了），所以至少有一条边e，e 在T1中，同时e不在T2中。这个与众不同的e就是我们的切入点。可以想象，如果我们把e在T1中去掉，T1就变成了两部分，即Ta和Tb，我们知道{Ta中的点}V{Tb中的点} = V（就是Ta中的点并上Tb中的点就是我们G中的点集V），所以在T2中，一定有一条边f（f！=e），f的一个点在{Ta中的点}，f的另一个点在{Tb中的点}。根据我们的Greedy算法Kruskal，我们没有选e，是因为e在我们的图中造成了回路。在进一步想，有回路是因为我们先选了f，这就说明cost(f) <= cost(e)。（恩，这就是我们的重点啊，笑一个O(∩_∩)O~）
下面的也就很显然了，我们考虑构造一棵新的树，T3，对于T3 = E(T1) - e + f，也就是T3中的边是
T1中的所有边除了e，同时加上边f。
1）很显然，我们知道T3是一棵spanning tree，f连通了由去掉e而分隔的两部分。
2）很显然，T3的cost是<= T1的cost的。因为cost(f) <= cost(e)，且其他不变。即T3是MST。
所以同个上面的构造，我们就构造出了一棵树，这个树是MST，同时它比T1更接近于T2。（多了一条common的边）
我们知道T1和T2对多有n条边是不同的，通过上面的步骤，我们可以经过n次变换，得到T2，同时cost <=T1，所以，T2是MST。证毕。
归纳法基本步骤
归纳法基本步骤 （一）第一数学归纳法： 一般地，证明一个与自然数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
高中数学归纳法证明题
高中数学归纳法证明题 高中数学归纳法证明题 1/2+2/2^2+3/2^3+......+n/2^n=2-n+2/2^n. 1/2+2/2^2+3/2^3+......+n/2^n=2-(n+2)/2^n. 1、当n=1时候， 左边=1/2; 右边=2-3/2=1/2 左边=右边，成立。 2、设n=k时候，有： 1/2+2/2^2+3/2^3+......+k/2^k=2-(k+2)/2^k成立， 则当n=k+1时候：有： 1/2+2/2^2+3/2^3+.....+k/2^k+(k+1)/2^(k+1) =2-(k+2)/2^k+(k+1)/2^(k+1) =2-[2(k+2)-(k+1)]/2^(k+1) =2-(k+3)/2^(k+1) =2-[(k+1)+2]/2^(k+1) 我觉得不是所有的猜想都非要用数学归纳法. 比如a1=2,a(n+1)/an=2,这显然是个等比数列 如果我直接猜想an=2^n,代入检验正确,而且对所有的n都成立,这时候干嘛还用数学归纳法啊.可是考试如果直接这样猜想是不得分的,必须要用数学归纳法证明.
结果带入递推公式验证是对n属于正整数成立. 用数学归纳法,无论n=1,还是n=k的假设,n=k+1都需要带入递推公式验证,不是多此一举吗.我又不是一个一个验证,是对n这个变量 进行验证,已经对n属于正整数成立了.怎么说就是错误的. 这说明你一眼能看出答案，是个本领。 然而，考试是要有过程的，这个本领属于你自己，不属于其他人，比如你是股票牛人，直接看出哪支会涨哪支会跌，但是不说出为什么，恐怕也不会令人信服。 比如你的问题，你猜想之后，代入检验，验证成功说明假设正确，这是个极端错误的数学问题，请记住：不是验证了一组答案通过， 就说明答案是唯一的!比如x+y=2.我们都知道这是由无数组解的方程。但是我猜想x=y=1,验证成功，于是得到答案，你觉得对吗?所 以你的证明方法是严格错误的! 说说你的这道题，最简单的一道数列题，当然可以一下看出答案，而且你的答案是正确的。但是证明起来就不是那么容易了，答案不 是看出来的，是算出来的。你的解法就是告诉大家，所有的答案都 是看出来，然后代入证明的。假设看不出来怎么办?那就无所适从， 永远也解不出来了!这就是你的做法带来的.答案，你想想呢?你的这 种做法有什么值得推广的? OK,了解! 数学归纳法使被证明了的，证明数学猜想的严密方法，这是毋庸置疑的。在n=1时成立;假设n=k成立，则n=k+1成立。这两个结论 确保了n属于N时成立，这是严密的。 你的例题太简单，直接用等比数列的定义就可以得到答案(首项 和公比均已知)，不能说明你的证明方法有误。我的本意是：任何一 种证明方法，其本身是需要严格证明的，数学归纳法是经过严格证 明的;而你的证明方法：猜想带入条件，满足条件即得到猜想正确的 结论。未经证明，(即使它很严密，我说即使)它不被别人认可。事 实上，你的证明方法(猜想带入所有条件均成立)只能得到“必要”
数学归纳法证明及其使用技巧
步骤 第一数学归纳法 一般地,证明一个与自然数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,n=n1时P(n)成立; (2)假设n≤k时命题成立,并在此基础上,推出n=k+1命题也成立。 综合(1)(2),对一切自然数n(≥n0),命题P(n)都成立。 倒推归纳法 又名反向归纳法 (1)验证对于无穷多个自然数n命题P(n)成立(无穷多个自然数可以就是一 个无穷数列中的数,如对于算术几何不等式的证明,可以就是2^k,k≥1); (2)假设P(k+1)(k≥n0)成立,并在此基础上,推出P(k)成立, 综合(1)(2),对一切自然数n(≥n0),命题P(n)都成立; 螺旋式归纳法 对两个与自然数有关的命题P(n),Q(n), (1)验证n=n0时P(n)成立; (2)假设P(k)(k>n0)成立,能推出Q(k)成立,假设 Q(k)成立,能推出 P(k+1) 成立; 综合(1)(2),对一切自然数n(≥n0),P(n),Q(n)都成立。 应用 1确定一个表达式在所有自然数范围内就是成立的或者用于确定一个其她的形式在一个无穷序列就是成立的。 2数理逻辑与计算机科学广义的形式的观点指出能被求出值的表达式就是等价表达式。
3证明数列前n项与与通项公式的成立。 4证明与自然数有关的不等式。 变体 在应用,数学归纳法常常需要采取一些变化来适应实际的需求。下面介绍一些常见的数学归纳法变体。 从0以外的数字开始 如果我们想证明的命题并不就是针对全部自然数,而只就是针对所有大于等于某个数字b的自然数,那么证明的步骤需要做如下修改: 第一步,证明当n=b时命题成立。第二步,证明如果n=m(m≥b)成立,那么可以推导出n=m+1也成立。 用这个方法可以证明诸如“当n≥3时,n^2>2n”这一类命题。 针对偶数或奇数 如果我们想证明的命题并不就是针对全部自然数,而只就是针对所有奇数或偶数,那么证明的步骤需要做如下修改: 奇数方面: 第一步,证明当n=1时命题成立。第二步,证明如果n=m成立,那么可以推导出n=m+2也成立。 偶数方面: 第一步,证明当n=0或2时命题成立。第二步,证明如果n=m成立,那么可以推导出n=m+2也成立。 递降归纳法 数学归纳法并不就是只能应用于形如“对任意的n”这样的命题。对于形如“对任意的n=0,1,2,、、、,m”这样的命题,如果对一般的n比较复杂,而n=m 比较容易验证,并且我们可以实现从k到k-1的递推,k=1,、、、,m的话,我们就能应用归纳法得到对于任意的n=0,1,2,、、、,m,原命题均成立。如果命题P(n)在n=1,2,3,、、、、、、,t时成立,并且对于任意自然数k,由 P(k),P(k+1),P(k+2),、、、、、、,P(k+t-1)成立,其中t就是一个常量,那么P(n)对于一切自然数都成立、 跳跃归纳法
数学归纳法+直接证明与间接证明
数学归纳法+直接证明与间接证明 题型一：数学归纳法基础 1、已知n 为正偶数，用数学归纳法证明111111112( ) 2 3 4 1 2 4 2n n n n -+-++ =+ ++ -++ 时，若已假设2(≥=k k n 为偶数） 时命题为真，则还需要用归纳假设再证 （） A ．1+=k n 时等式成立 B ．2+= k n 时等式成立 C ．2 2+=k n 时等式成立 D ．)2(2+=k n 时等式成立 2、已知n 是正偶数，用数学归纳法证明时，若已假设n=k （2≥k 且为偶数） 时命题为真，，则还需证明（ ） A.n=k+1时命题成立 B. n=k+2时命题成立 C. n=2k+2时命题成立 D. n=2（k+2）时命题成立 3、某个命题与正整数n 有关，如果当)(+∈=N k k n 时命题成立，那么可推得当1+= k n 时命题也成立. 现已知当7 =n 时该命题不成立，那么可推得（） A ．当n=6时该命题不成立 B ．当n=6时该命题成立 C ．当n=8时该命题不成立 D ．当n=8时该命题成立 4、利用数学归纳法证明 “*),12(312)()2)(1(N n n n n n n n ∈-???????=+???++ ”时，从“k n =”变到 “1+=k n ”时，左边应增乘的因式是 （ ） A 12+k B 1 12++k k C 1 ) 22)(12(+++k k k D 1 32++k k 5、用数学归纳法证明),1(1112 2 * +∈≠--= ++++N n a a a a a a n n ，在验证 n=1时， 左边计算所得的式子是（ ） A. 1 B.a +1 C.21a a ++ D. 421a a a +++ 典例分析
数学归纳法证明例题
例1.用数学归纳法证明： ()()12121217 51531311+=+-++?+?+?n n n n ． 请读者分析下面的证法: 证明：①n ＝1时,左边31311=?=，右边3 1121=+=,左边=右边,等式成立. ②假设n =ｋ时，等式成立,即: ()()12121217 51531311+=+-++?+?+?k k k k . 那么当n =ｋ+1时,有: ()()()()32121121217 51531311++++-++?+?+?k k k k ????????? ??+-++??? ??+--++??? ??-+??? ??-+??? ? ?-=3211211211217151513131121k k k k 322221321121++?=??? ??+-= k k k ()1 121321+++=++=k k k k 这就是说,当n ＝k +1时，等式亦成立． 由①、②可知，对一切自然数n 等式成立． 评述：上面用数学归纳法进行证明的方法是错误的，这是一种假证，假就假在没有利用归纳假设ｎ=k 这一步,当ｎ=k +1时，而是用拆项法推出来的，这样归纳假设起到作用，不符合数学归纳法的要求． 正确方法是：当n ＝ｋ+1时. ()()()()32121121217 51531311++++-++?+?+?k k k k ()() 3212112++++=k k k k
()()()()()() 321211232121322++++=++++=k k k k k k k k ()1 121321+++=++=k k k k 这就说明,当n ＝k +１时,等式亦成立, 例２.是否存在一个等差数列｛a ｎ},使得对任何自然数n ，等式: a 1+2a ２＋3a ３+…+n ａn =ｎ（n ＋１）(n +2) 都成立，并证明你的结论. 分析：采用由特殊到一般的思维方法,先令ｎ=1,２，3时找出来｛a n },然后再证明一般性. 解：将ｎ=1,２，3分别代入等式得方程组． ?????=++=+=603224 26321 211a a a a a a , 解得a 1=6，a 2=9，a ３=1２，则d ＝３． 故存在一个等差数列a n =3n +３，当n ＝1，２,３时,已知等式成立． 下面用数学归纳法证明存在一个等差数列a n =3n +3,对大于3的自然数，等式 ａ１+２a 2+3ａ3+…＋ｎa n =n (n +１）(n +２)都成立. 因为起始值已证，可证第二步骤. 假设n =ｋ时,等式成立，即 a 1+2a ２＋３a 3+…+ka k =k （ｋ+1）(k ＋2) 那么当ｎ=k +１时， ａ1+2a 2＋3a 3+…＋ka k ＋(ｋ+１)ａk +1 = ｋ(k +1)（k +２)+ (k +1)[３(ｋ+1)+3] =(k ＋1)(k ２+2k +3k +6) =(k +１）(k +２）(k +3） =(k +1)[(k +1)+1][(k +1)+2] 这就是说，当ｎ=k +1时,也存在一个等差数列ａn =３n +3使a 1+２a 2+３a 3+…+n ａｎ=n （n +１)(ｎ+2)成立. 综合上述,可知存在一个等差数列ａn =3n +3，对任何自然数n ，等式a 1＋2a 2+3a 3+…+na ｎ=ｎ（ｎ+1)(n +2)都成立.
归纳法证明不等式
归纳法证明不等式 数学归纳法证明不等式的本质 数学归纳法证明不等式的典型类型是与数列或数列求和有关的问题，凡是与数列或数列求和有关的问题都可统一表述成f(n)?g(n)(n?n?)的形式或近似于上述形式。 这种形式的关键步骤是由n?k时，命题成立推导n?k?1时，命题也成立。为了表示的方便，我们记?左n?f(k?1)?f(k)，?右n?g(k?1)?g(k)分别叫做左增量，右增量。那么，上述证明的步骤可表述为 f(k?1)?f(k)??左k?g(k)??左k?g(k)??右k?g(k?1) 例1．已知an?2n?1，求证： 本题要证后半节的关键是证 an1a1a2n????n?(n?n?) 23a2a3an?12 2k?1?11?中k??右k即证k?2? 2?12 而此式显然成立，所以可以用数学归纳法证明。 而要证前半节的关键是证 12k?1?1?左k??中k即证?k?2 22?1 而此式显然不成立，所以不能用数学归纳法证明。如果不进行判断就用数学归纳法证前半节，忙乎半天，只会徒劳。 有时，f(n)?g(n)(n?n?)中f(n),g(n)是以乘积形式出现，且f(n)?0,g(n)?0是显然成立的。此时，可记 ?左k?f(k?1)g(k?1)，?右k? f(k)g(k) 分别叫做左增倍，右增倍。那么，用数学归结法证明由n?k时，成立推导 n?k?1成立，可表述为 f(k?1)?f(k)??左k?g(k)??左k?g(k)??右k?g(k?1) 和前面所讲相似，上述四步中，两个“=”和“<”都显然成立，而“≤”是否成立，就需要判断和证明了，既“?左k??右k”若成立，既可用数学归纳法证明；若不成立，则不能用数学归纳法证明。因此，可以这样说，此时，数学归纳法证明不等式的本质是证“左增倍≤右增倍”，而判断能否用数学归纳法证明不等式的标准就是看“左增倍≤右增倍”是否成立。 第二篇：归纳法证明不等式
数学归纳法知识点大全
数学归纳法 数学归纳法是用于证明与正整数n 有关的数学命题的正确性的一种严格的推理方法．在数学竞赛中占有很重要的地位． （1）第一数学归纳法 设)(n P 是一个与正整数有关的命题，如果 ① 0n n =（N n ∈01．数学归纳法的基本形式）时，)(n P 成立； ②假设),(0N k n k k n ∈≥=成立，由此推得1+=k n 时，)(n P 也成立，那么，根据①②对一切正整数0n n ≥时，)(n P 成立． （2）第二数学归纳法 设)(n P 是一个与正整数有关的命题，如果 ①当0n n =（N n ∈0）时，)(n P 成立； ②假设),(0N k n k k n ∈≥≤成立，由此推得1+=k n 时，)(n P 也成立，那么，根据①②对一切正整数0n n ≥时，)(n P 成立． 2．数学归纳法的其他形式 （1）跳跃数学归纳法 ①当l n ,,3,2,1Λ=时，)(,),3(),2(),1(l P P P P Λ成立，
②假设k n =时)(k P 成立，由此推得l k n +=时，)(n P 也成立，那么，根据①②对一切正整数1≥n 时，)(n P 成立． （2）反向数学归纳法 设)(n P 是一个与正整数有关的命题，如果 ① )(n P 对无限多个正整数n 成立； ②假设k n =时，命题)(k P 成立，则当1-=k n 时命题)1(-k P 也成立，那么根据①②对一切正整数1≥n 时，)(n P 成立． 例如，用数学归纳法证明： 为非负实数，有 在证明中，由 真，不易证出 真；然而却很容易证出 真，又容易证明不等式对无穷多个 （只要 型的自然数）为真；从而证明 ，不等式成立． （3）螺旋式归纳法 P （n ），Q （n ）为两个与自然数 有关的命题，假如 ①P(n0)成立； ②假设 P(k) (k>n0)成立，能推出Q(k)成立，假设 Q(k)成立，能推出 P(k+1)成立； 综合（1）（2）,对于一切自然数n （>n0），P(n),Q(n)都成立；
数学归纳法
数学归纳法 知识点数学归纳法 证明一个与正整数n有关的命题，可按下列步骤进行： (1)(归纳奠基)证明当n取第一个值n0(n0∈N*)时命题成立． (2)(归纳递推)假设n＝k(k≥n0，k∈N*)时命题成立，证明当n＝k＋1时命题也成立． 只要完成这两个步骤，就可以断定命题对从n0开始的所有正整数n都成立．7 易误提醒运用数学归纳法应注意： (1)第一步验证n＝n0时，n0不一定为1，要根据题目要求选择合适的起始值． (2)由n＝k时命题成立，证明n＝k＋1时命题成立的过程中，一定要用到归纳假设，否则就不是数学归纳法． 1．利用数学归纳法证明问题时有哪些注意事项？ 剖析：(1)用数学归纳法证明有关命题的关键在第二步，即n＝k＋1时命题为什么成立？n＝k＋1时命题成立是利用假设n＝k时命题成立，根据有关的定理、定义、公式、性质等数学结论推证出来的，而不是直接代入，否则n＝k＋1时命题成立也成假设了，命题并没有得到证明． (2)用数学归纳法可证明有关的正整数问题，但并不是所有的正整数问题都能用数学归纳法证明，学习时要具体问题具体分析． 2．运用数学归纳法时易犯的错误有哪些？ 剖析：(1)对项数估算的错误，特别是寻找n＝k与n＝k＋1的关系时，项数发生什么变化被弄错． (2)没有利用归纳假设：归纳假设是必须要用的．假设是起桥梁作用的，桥梁断了就通不过去了． (3)关键步骤含糊不清，“假设n＝k时结论成立，利用此假设证明n＝k＋1时结论也成立”是数学归纳法的关键一步，也是证明问题中最重要的环节，对推导的过程要把步骤写完整，注意证明过程的严谨性、规范性．
【自主练习】 1．已知f (n )＝1n ＋1n ＋1＋1n ＋2＋…＋1 n 2，则( ) A ．f (n )中共有n 项，当n ＝2时，f (2)＝12＋1 3 B ．f (n )中共有n ＋1项，当n ＝2时，f (2)＝12＋13＋1 4 C ．f (n )中共有n 2－n 项，当n ＝2时，f (2)＝12＋1 3 D ．f (n )中共有n 2－n ＋1项，当n ＝2时，f (2)＝12＋13＋1 4 2．(2016·黄山质检)已知n 为正偶数，用数学归纳法证明1－12＋13－14＋…＋1 n ＋1＝ 2? ???1n ＋2＋1n ＋4＋…＋12n 时，若已假设n ＝k (k ≥2为偶数)时命题为真，则还需要用归纳假设再证n ＝( )时等式成立( ) A ．k ＋1 B ．k ＋2 C ．2k ＋2 D ．2(k ＋2)
数学归纳法证明例题
例1．用数学归纳法证明： ()()12121217 51531311+=+-++?+?+?n n n n ． 请读者分析下面的证法： 证明：①n =1时，左边31311=?=，右边3 1121=+=，左边=右边，等式成立． ②假设n =k 时，等式成立，即： ()()12121217 51531311+=+-++?+?+?k k k k ． 那么当n =k +1时，有： ()()()()32121121217 51531311++++-++?+?+?k k k k ????????? ??+-++??? ??+--++??? ??-+??? ??-+??? ? ?-=3211211211217151513131121k k k k 322221321121++?=??? ??+-= k k k ()1 121321+++=++=k k k k 这就是说，当n =k +1时，等式亦成立． 由①、②可知，对一切自然数n 等式成立． 评述：上面用数学归纳法进行证明的方法是错误的，这是一种假证，假就假在没有利用归纳假设n =k 这一步，当n =k +1时，而是用拆项法推出来的，这样归纳假设起到作用，不符合数学归纳法的要求． 正确方法是：当n =k +1时． ()()()()32121121217 51531311++++-++?+?+?k k k k ()() 3212112++++=k k k k
()()()()()() 321211232121322++++=++++=k k k k k k k k ()1 121321+++=++=k k k k 这就说明，当n =k +1时，等式亦成立， 例2．是否存在一个等差数列{a n }，使得对任何自然数n ，等式： a 1+2a 2+3a 3+…+na n =n (n +1)(n +2) 都成立，并证明你的结论． 分析：采用由特殊到一般的思维方法，先令n =1，2，3时找出来{a n }，然后再证明一般性． 解：将n =1，2，3分别代入等式得方程组． ?????=++=+=603224 26321 211a a a a a a ， 解得a 1=6，a 2=9，a 3=12，则d =3． 故存在一个等差数列a n =3n +3，当n =1，2，3时，已知等式成立． 下面用数学归纳法证明存在一个等差数列a n =3n +3，对大于3的自然数，等式 a 1+2a 2+3a 3+…+na n =n (n +1)(n +2)都成立． 因为起始值已证，可证第二步骤． 假设n =k 时，等式成立，即 a 1+2a 2+3a 3+…+ka k =k (k +1)(k +2) 那么当n =k +1时， a 1+2a 2+3a 3+…+ka k +(k +1)a k +1 = k (k +1)(k +2)+ (k +1)[3(k +1)+3] =(k +1)(k 2+2k +3k +6) =(k +1)(k +2)(k +3) =(k +1)[(k +1)+1][(k +1)+2] 这就是说，当n =k +1时，也存在一个等差数列a n =3n +3使a 1+2a 2+3a 3+…+na n =n (n +1)(n +2)成立． 综合上述，可知存在一个等差数列a n =3n +3，对任何自然数n ，等式a 1+2a 2+3a 3+…
归纳法证明思路分析及转化策略
从k 到(k ＋1)思路受阻分析及转化策略 用数学归纳法证明不等式，特别是数列不等时，是一个行之有效的方法，也是中等数学中的一个基本方法，近些年高考试题中多次出现这类考题．运用这种方法证明不等式时，往往有好多学生在证k 到(k ＋1)的过程中，卡了壳，断了思路，这是一种普遍现象．下面分析一下思路受阻几种原因及转化策略． 一、从k 到(k ＋1)添项不足 在从k 到(k ＋1)的证明过程中，如果分析不透命题结构，就会造成添项不足，证明夭折． 例1 已知S n =1＋12＋13＋…＋1n (n ∈N*)，用数学归纳法证明2n S ＞1＋2 n (n ≥2，n ∈N*)． 思路受阻过程： (i)当n = 2时，22S =1＋ 12＋13＋14=1＋1312＞1＋2 2 ，命题成立． (ii)设n = k (k ≥2)时不等式成立，即2k S =1＋12＋13＋…＋1 2k ＞1＋2k ，则当n = k ＋1时， 12k S +=1＋12＋13＋…＋12k ＋112k +＞1＋2k ＋1 12 k +， 要证明12k S +＞1＋1 2 k +， 只须证1＋2k ＋11 2k +＞1＋12k +， 即证11 2 k +＞12． 显然，当k ≥2时这是不可能的，解题思路受到阻碍． 受阻原因分析： 由于S n =1＋ 12＋13＋…＋1n ， 所以12k S +=1＋12＋13＋…＋12 k ＋121k +＋122k +＋…＋1121k +-＋11 2k +， 即12k S +=2k S ＋211 12122 22k k k k k ++++++项 ＞1＋2 k ＋1112111222k k k k ++++++项 =1＋2 k ＋122k k +． 这就是说，由k 到(k ＋1)时，增加了2k 项，而不仅仅是1项(1 1 2 k +)．如果把这个结构搞错了，证题思路也就中断了．这就是前面思路受阻的根本原因．
数学归纳法经典例题详解
例1．用数学归纳法证明： ()()12121217 51531311+=+-++?+?+?n n n n ． 请读者分析下面的证法： 证明：①n =1时，左边31311=?=，右边3 1121=+=，左边=右边，等式成立． ②假设n =k 时，等式成立，即： ()()12121217 51531311+=+-++?+?+?k k k k ． 那么当n =k +1时，有： ()()()()32121121217 51531311++++-++?+?+?k k k k ????????? ??+-++??? ??+--++??? ??-+??? ??-+??? ? ?-=3211211211217151513131121k k k k 322221321121++?=??? ??+-= k k k ()1 121321+++=++=k k k k 这就是说，当n =k +1时，等式亦成立． 由①、②可知，对一切自然数n 等式成立． 评述：上面用数学归纳法进行证明的方法是错误的，这是一种假证，假就假在没有利用归纳假设n =k 这一步，当n =k +1时，而是用拆项法推出来的，这样归纳假设起到作用，不符合数学归纳法的要求． 正确方法是：当n =k +1时． ()()()()32121121217 51531311++++-++?+?+?k k k k ()() 3212112++++=k k k k ()()()()()() 321211232121322++++=++++=k k k k k k k k
()1 121321+++=++=k k k k 这就说明，当n =k +1时，等式亦成立， 例2．是否存在一个等差数列{a n }，使得对任何自然数n ，等式： a 1+2a 2+3a 3+…+na n =n (n +1)(n +2) 都成立，并证明你的结论． 分析：采用由特殊到一般的思维方法，先令n =1，2，3时找出来{a n }，然后再证明一般性． 解：将n =1，2，3分别代入等式得方程组． ?????=++=+=603224 26321 211a a a a a a ， 解得a 1=6，a 2=9，a 3=12，则d =3． 故存在一个等差数列a n =3n +3，当n =1，2，3时，已知等式成立． 下面用数学归纳法证明存在一个等差数列a n =3n +3，对大于3的自然数，等式 a 1+2a 2+3a 3+…+na n =n (n +1)(n +2)都成立． 因为起始值已证，可证第二步骤． 假设n =k 时，等式成立，即 a 1+2a 2+3a 3+…+ka k =k (k +1)(k +2) 那么当n =k +1时， a 1+2a 2+3a 3+…+ka k +(k +1)a k +1 = k (k +1)(k +2)+ (k +1)[3(k +1)+3] =(k +1)(k 2+2k +3k +6) =(k +1)(k +2)(k +3) =(k +1)[(k +1)+1][(k +1)+2] 这就是说，当n =k +1时，也存在一个等差数列a n =3n +3使a 1+2a 2+3a 3+…+na n =n (n +1)(n +2)成立． 综合上述，可知存在一个等差数列a n =3n +3，对任何自然数n ，等式a 1+2a 2+3a 3+…+na n =n (n +1)(n +2)都成立． 例3．证明不等式n n 21 31 21 1<++++ (n ∈N)． 证明：①当n =1时，左边=1，右边=2．
数学归纳法证明例题
数学归纳法例题 例 请读者分析下面的证法： 证明：①n =1时，左边31311=?=，右边3 1121=+=，左边=右边，等式成立． ②假设n =k 时，等式成立，即： ()()12121217 51531311+=+-++?+?+?k k k k ． 那么当n =k +1时，有： ()()()()32121121217 51531311++++-++?+?+?k k k k ????????? ??+-++??? ??+--++??? ??-+??? ??-+??? ? ?-=3211211211217151513131121k k k k 3 22221321121++?=??? ??+-=k k k ()1 121321+++=++=k k k k 这就是说，当n =k +1时，等式亦成立． 由①、②可知，对一切自然数n 等式成立． 评述：上面用数学归纳法进行证明的方法是错误的，这是一种假证，假就假在没有利用归纳假设n =k 这一步，当n =k +1时，而是用拆项法推出来的，这样归纳假设起到作用，不符合数学归纳法的要求． 正确方法是：当n =k +1时． ()()()()32121121217 51531311++++-++?+?+?k k k k ()() 3212112++++=k k k k ()()()()()() 321211232121322++++=++++=k k k k k k k k
()1 121321+++=++=k k k k 这就说明，当n =k +1时，等式亦成立， 例2．是否存在一个等差数列{a n }，使得对任何自然数n ，等式： a 1+2a 2+3a 3+…+na n =n (n +1)(n +2) 都成立，并证明你的结论． 分析：采用由特殊到一般的思维方法，先令n =1，2，3时找出来{a n }，然后再证明一般性． 解：将n =1，2，3分别代入等式得方程组． ?????=++=+=603224 26321 211a a a a a a ， 解得a 1=6，a 2=9，a 3=12，则d =3． 故存在一个等差数列a n =3n +3，当n =1，2，3时，已知等式成立． 下面用数学归纳法证明存在一个等差数列a n =3n +3，对大于3的自然数，等式 a 1+2a 2+3a 3+…+na n =n (n +1)(n +2)都成立． 因为起始值已证，可证第二步骤． 假设n =k 时，等式成立，即 a 1+2a 2+3a 3+…+ka k =k (k +1)(k +2) 那么当n =k +1时， a 1+2a 2+3a 3+…+ka k +(k +1)a k +1 = k (k +1)(k +2)+ (k +1)[3(k +1)+3] =(k +1)(k 2+2k +3k +6) =(k +1)(k +2)(k +3) =(k +1)[(k +1)+1][(k +1)+2] 这就是说，当n =k +1时，也存在一个等差数列a n =3n +3使a 1+2a 2+3a 3+…+na n =n (n +1)(n +2)成立． 综合上述，可知存在一个等差数列a n =3n +3，对任何自然数n ，等式a 1+2a 2+3a 3+…+na n =n (n +1)(n +2)都成立．
数学归纳法证题步骤与技巧实战篇
数学归纳法证题步骤与技巧 在数学问题中，有一类问题是与自然数有关的命题。自然数有无限多个，不可能就所有自然数—一加以验证，所以用完全归纳法是不可能的。但就部分自然数进行验证即用不完全归纳法得到的结论，又是不可靠的。这就需要寻求证明这一类命题的一种切实可行而又满足逻辑严谨性要求的新方法——数学归纳法。1.数学归纳法的范围 数学归纳法是以自然数的归纳公理做为它的理论基础的。因此，数学归纳法的适用范围仅限于与自然数有关的命题。它能帮助我们判断种种与自然数n有关的猜想的正确性。 2.数学归纳法两个步骤的关系 第一步是递推的基础，第二步是递推的根据，两个步骤缺一不可，有第一步无第二表，属于不完全归纳法，论断的普遍性是不可靠的；有第二步无第一步中，则第二步中的假设就失去了基础。只有把第一步结论与第二步结论联系在一起，才可以断定命题对所有的自然数n都成立。 3.第二数学归纳法 第二数学归纳法的证明步骤是： 证明当n=1时命题是正确的； ②k为任意自然数，假设n＜k时命题都是正确的，如果我们能推出n=时命题也正确，就可以肯定该命题对一切自然数都正确。数学归纳法和第二归纳法是两个等价的归纳法，我们把数学归纳法也叫做第一归纳法。有些命题用第一归纳法证明不大方便，可以用第二归纳法证明。 4.数学归纳法的原理 数学归纳法证明的是与自然数有关的命题，它的依据是皮亚诺提出的自 然数的序数理论，就是通常所说的自然数的皮亚诺公理，内容是： （1）l是自然数。 （2）每个自然数a有一个确定的“直接后继”数a’，a也是自然数。 （2）a’≠1，即1不是任何自然数的“直接后继”数。 （4）由a’=b’，推得a=b，即每个自然数只能是另外的唯一自然的“直接后继” 数。 （5）任一自然数的集合，如果包含1，并且假设包含a，也一定包含a的“直接后继”数a’，则这个集合包含所有的自然数。皮亚诺公理中的（5）是数学归纳法的依据，又叫归纳公理数学归纳法的应用及举例。 2k+1k+2 因为由假设知4 +3能被13整除，13·42k+1也能被13整除，这就是说，当n=k ＋1时，f（k＋l）能被13整除。根据（1）、（2），可知命题对任何n∈N都成立。下面按归纳步中归纳假设的形式向读者介绍数学归纳法的几种不同形式以及它们的应用。 （l）简单归纳法。即在归纳步中，归纳假设为“n=k时待证命题成立”。这是最
专题20 数学归纳法及其证明(解析版)
专题20 数学归纳法及其证明 1、（2017浙江）已知数列{}n x 满足：11x =，11ln(1)n n n x x x ++=++()n ∈* N ． 证明：当n ∈*N 时 （Ⅰ）10n n x x +<<； （Ⅱ）1 122 n n n n x x x x ++-≤ ； （Ⅲ）1211 22 n n n x --≤≤． 【解析】（Ⅰ）用数学归纳法证明：0n x > 当1n =时，110x => 假设n k =时，0k x >， 那么1n k =+时，若10k x +≤，则110ln(1)0k k k x x x ++<=++≤，矛盾，故10k x +>． 因此0n x >()n ∈* N 所以111ln(1)n n n n x x x x +++=++> 因此10n n x x +<<()n ∈* N （Ⅱ）由111ln(1)n n n n x x x x +++=++>得 2 111111422(2)ln(1)n n n n n n n n x x x x x x x x ++++++-+=-+++ 记函数2 ()2(2)ln(1)(0)f x x x x x x =-+++≥ 函数()f x 在[0,)+∞上单调递增，所以()(0)f x f ≥=0， 因此 2 111112(2)ln(1)()0n n n n n x x x x f x +++++-+++=≥ 故1 12(N )2 n n n n x x x x n *++-∈≤ （Ⅲ）因为 11111ln(1)2n n n n n n x x x x x x +++++=+++=≤
所以112 n n x -≥得 由 1 122 n n n n x x x x ++-≥得 11111 2()022 n n x x +-->≥ 所以 1211111111 2()2()2222 n n n n x x x -----???-=≥≥≥ 故2 1 2n n x -≤ 综上，1211 (N )22 n n n x n *--∈≤≤ ． 2、（2016年江苏卷）. (1) 求7C 36－4C 47 的值； (2) 设m ，n ∈N *，n ≥m ，求证： (m ＋1)C m m ＋(m ＋2)C m m ＋1＋(m ＋3)C m m ＋2＋…＋n C m n －1＋(n ＋1)C m n ＝(m ＋1)C m ＋ 2 n ＋2. 规范解答 (1) 7C 36－4C 47＝7×6×5×43×2×1－4×7×6×5×44×3×2×1＝0. (2) 解法1 当n ＝m 时，结论显然成立．当n >m 时， (k ＋1)C m k ＝k ＋1·k ！m ！·k －m ！＝(m ＋1)·k ＋1！m ＋1！·[k ＋1－m ＋1]！＝(m ＋1)C m ＋1k ＋1，k ＝m ＋1，m ＋2，…，n . 又因为C m ＋ 1k ＋1＋C m ＋ 2k ＋1＝C m ＋ 2k ＋2， 所以(k ＋1)C m k ＝(m ＋1)(C m ＋ 2k ＋2－C m ＋ 2k ＋1)，k ＝m ＋1，m ＋2，…，n . 因此， (m ＋1)C m m ＋(m ＋2)C m m ＋1＋(m ＋3)C m m ＋2＋…＋(n ＋1)·C m n ＝(m ＋1)C m m ＋[(m ＋2)C m m ＋1＋(m ＋3)C m m ＋2＋…＋(n ＋1)·C m n ]＝(m ＋1)C m ＋ 2m ＋2＋(m ＋1)[(C m ＋ 2m ＋3－C m ＋ 2m ＋2)＋(C m ＋ 2m ＋4－C m ＋ 2m ＋3)＋…＋(C m ＋ 2n ＋2－C m ＋ 2n ＋1)]＝(m ＋1)C m ＋ 2 n ＋2. 解法2 对任意的m ∈N *， ①当n ＝m 时，左边＝(m ＋1)C m m ＝m ＋1，右边＝(m ＋1)C m ＋ 2 m ＋2＝m ＋1，等式成立， ②假设n ＝k (k ≥m )时命题成立， 即(m ＋1)C m m ＋(m ＋2)C m m ＋1＋(m ＋3)C m m ＋2＋…＋k C m k －1＋(k ＋1)C m k ＝(m ＋1)C m ＋ 2k ＋2， 当n ＝k ＋1时，左边＝(m ＋1)C m m ＋(m ＋2)C m m ＋1＋(m ＋3)C m m ＋2＋…＋k C m k －1＋(k ＋1)C m k ＋(k ＋2)C m k ＋1＝(m ＋1)·C m ＋ 2k ＋2＋(k ＋2)C m k ＋1， 右边＝(m ＋1)C m ＋ 2 k ＋3， 而(m ＋1)C m ＋ 2k ＋3－(m ＋1)C m ＋ 2k ＋2＝(m ＋1)× k ＋3！ m ＋2！k －m ＋1！－ k ＋2！ m ＋2！k －m ！ ＝(m ＋
用数学归纳法证明不等式
人教版选修4—5不等式选讲 课题：用数学归纳法证明不等式 教学目标： 1、牢固掌握数学归纳法的证明步骤，熟练表达数学归纳法证明的过程。 2、通过事例，学生掌握运用数学归纳法，证明不等式的思想方法。 3、培养学生的逻辑思维能力，运算能力和分析问题，解决问题的能力。 重点、难点： 1、巩固对数学归纳法意义和有效性的理解，并能正确表达解题过程，以及掌握用数学归纳法证明不等式的基本思路。 2、应用数学归纳法证明的不同方法的选择和解题技巧。 教学过程： 一、复习导入： 1、上节课学习了数学归纳法及运用数学归纳法解题的步骤，请同学们回顾，说出数学归纳法的步骤？ （1）数学归纳法是用于证明某些与自然数有关的命题的一种方法。 （2）步骤：1）归纳奠基; 2）归纳递推。 2、作业讲评：（出示小黑板） 习题：用数学归纳法证明：2+4+6+8+……+2n=n(n+1) 如采用下面的证法，对吗？ 证明：①当n=1时，左边=2=右边，则等式成立。 ②假设n=k时，（k∈N，k≥1）等式成立，
即2+4+6+8+……+2k=k(k+1) 当n=k+1时， 2+4+6+8+……+2k+2(k+1) ∴n=k+1时，等式成立。 由①②可知，对于任意自然数n，原等式都成立。 （1）学生思考讨论。 （2）师生总结：1）不正确 2）因为在证明n=k+1时，未用到归纳假设，直接用等差数列求和公式，违背了数学归纳法本质：递推性。 二、新知探究 明确了数学归纳法本质，我们共同讨论如何用数学归纳法证明不等式。 (出示小黑板) 例1 观察下面两个数列，从第几项起a n始终小于b n？证明你的结论。 ｛a n=n2｝:1,4,9,16,25,36,49,64,81, …… ｛b n=2n｝:2,4,8,16,32,64,128,256,512, …… （1）学生观察思考 （2）师生分析 （3）解：从第5项起，a n＜b n，即n2＜2n,n∈N+（n≥5） 证明：（1）当n=5时，有52＜25，命题成立。 （2）假设当n=k（k≥5）时命题成立即k2＜2k ?你能说出证明中每一步的理由吗？
用数学归纳法证明
用数学归纳法证明 用数学归纳法证明1/2+2/2^2+3/2^3+......+n/2^n=2 - n+2/2^n. 1/2+2/2^2+3/2^3+......+n/2^n=2 - (n+2)/2^n. 1、当n=1时候， 左边=1/2; 右边=2-3/2=1/2 左边=右边，成立。 2、设n=k时候，有： 1/2+2/2^2+3/2^3+......+k/2^k=2 - (k+2)/2^k成立， 则当n=k+1时候：有： 1/2+2/2^2+3/2^3+.....+k/2^k+(k+1)/2^(k+1) =2 - (k+2)/2^k+(k+1)/2^(k+1) =2-[2(k+2)-(k+1)]/2^(k+1) =2-(k+3)/2^(k+1) =2-[(k+1)+2]/2^(k+1) 得证。 我觉得不是所有的猜想都非要用数学归纳法. 比如a1=2,a(n+1)/an=2,这显然是个等比数列 如果我直接猜想an=2^n,代入检验正确,而且对所有的n都成立,这时候干嘛还用数学归纳法啊.可是考试如果直接这样猜想是不得分的,
必须要用数学归纳法证明. 我觉得如果是数列求和,猜想无法直接验证,需要数学归纳法,这个是可以接受的.但是上面那种情况,谁能告诉我为什么啊.我觉得逻辑已经是严密的了. 结果带入递推公式验证是对n属于正整数成立. 用数学归纳法,无论n=1,还是n=k的假设,n=k+1都需要带入递推公式验证,不是多此一举吗.我又不是一个一个验证,是对n这个变量进行验证,已经对n属于正整数成立了.怎么说就是错误的. 怎么又扯到思维上了,论严密性我比谁都在意,虽然是猜出来的,毕竟猜想需要,我的问题是--------这样的验证方式严不严密,在没有其 他直接证明方法的情况下,是不是一定要用数学归纳法-------,并没有说这样就是对待数学的态度,没有猜想数学怎么发展. 这说明你一眼能看出答案，是个本领。 然而，考试是要有过程的，这个本领属于你自己，不属于其他人，比如你是股票牛人，直接看出哪支会涨哪支会跌，但是不说出为什么，恐怕也不会令人信服。 比如你的问题，你猜想之后，代入检验，验证成功说明假设正确，这是个极端错误的数学问题，请记住：不是验证了一组答案通过，就说明答案是唯一的!比如x + y = 2.我们都知道这是由无数组解的方程。但是我猜想x=y=1,验证成功，于是得到答案，你觉得对吗?所以你的证明方法是严格错误的! 你的这种思想本身就是经不起推敲的，学习数学不是会做多少题，而