数学归纳法的应用

2017-05-26

数学归纳法的应用非常广泛,在实际的教学研究中也得到了很大的重视 接下来小编为你整理了数学归纳法的应用,一起来看看吧。

数学归纳法的原理

数学归纳法是一种研究与自然数有关的证明,它可以巧妙的证明结果含有n的结论。它避免了无穷次的步骤推导引起的逻辑问题,是一种严格的演绎推理,所以它与普通的归纳法有着很大的区别。已知最早的使用数学归纳法的证明出现于F·莫罗利科(Francesco Maurolico)的《算数》(Arithmeticorum libri duo)(1575AD)。莫罗利科利用递推关系巧妙地证明出前n个奇数的总和是n^2,由此总结出了数学归纳法。

数学归纳法最基本格式为:(1)n= n0时,成立。(2)假设n= k时成立,当n=k+1时命题也成立。于是根据(1)(2)可知命题对于任意n成立。举个例子,就像一排多米诺骨牌(这个例子很经典形象),我们知道第一个被推倒了,我们也知道每一个与之相邻的下一个骨牌要倒,那么你就可以推断所有的的骨牌都将要倒。

如:证1+2+3+„+n=n*(n+1)/2 。按顺序1.当n=1时,显然成立。2.假设n=k时成立,当n=k+1时,S= k*(k+1)/2+(k+1) = (k+2) (k+1)/2. 于是结果成立。

数学归纳法的应用

1. 所有马都一个颜色。(即任意n匹马都只有一个颜色)

证:当只有1匹马,命题成立。假设任意k匹马都只有一个颜色,当n=k+1时,我从中任意挑取k匹马,这k匹马颜色相同;我再用剩下的那只马去换掉这群马中的任意一只,组成新的马群,依然有k匹马,颜色还是相同;根据集合交并原理,可知k+1时也成立。证毕。

原来真的所有马都一种颜色吗?怎么可能!现在,我们来分析一下究竟是哪里出的错。我们可以看到,在第二步,当k=1时,两匹马不能出现交集,不能推出k=2时成立。这个证明链在第二节断掉了,虽然后面是连着的,但却推不出正确结论了。所以这提示我们,即使前面第一步证明了n=1成立,第二步依然要保证n=k对任意所涉及的数也成立,包括1.

2.n人一人一顶帽子,有m顶白帽子,其余都是黑帽子。每次敲钟,都要求所有能判断自己为白帽子的人离开。正在这n个无聊的人苦苦思索的时候,突然来了一个人,说:“这里居然有人带白帽子!”,然后飘走了。黑帽子的人很想说“废话!”,却发现过了一会所有白帽子的人都走了(他们判断出自己的帽子颜色了),这是怎么回事?

好吧,我们还是用数学归纳法做一做:

命题1:我们假设只有1人白帽子,他发现所有人都戴黑帽子,当飘走的那个人说完话后,他可以立刻知道自己是白的。于是第1声钟响后这1个白帽可确认。

命题2:假设只有2个人白,其中一个人发现有只有1个人白帽,如果命题1成立,即只有他是白帽,他应该钟响1下后立刻离开,可他不走。所以说明命题1不成立,一定有2个白帽——自己和他!于是第2声钟响后这2个白帽可确认。

假设命题k成立,命题n=k+1时,假设只有k+1个白帽,其中一人发现:有k个白帽,如果是命题k,他们在第k声钟响后应该全部离开,可是没走,所以一定自己是白帽子让他们不能判断。于是在第k+1声钟响后,k+1白帽可全部确认离开。结论成立。

所以,那句废话虽然对黑帽子没有,但对白帽子而言是却是归纳法的第一块多米诺骨牌。

3.在《不可思议?》这本书里还有一个更那啥的题,经改编如下:有一个杀人狂把两个人分别关在两个密室,分别告诉他们两个相邻正自然数,两个人虽然知道数字相邻,却不知道对方的数。计时开始后,每分钟他们都有一次机会选择确认按钮,确认的消息可以被双方听见。只有知道另一方数字是多少的人才能出去。快快,生路在哪里?

这看起来好像无解,假如我知道自己的数是27,怎么判断对方究竟是26还是28,难道出去的概率是50%?

不,概率是100%,唯一的生路在那个每分钟一次确认按钮上(且确认消息可通知双方)。当A的数是1,则在第1分钟便可知道B的数是2(因为不是0)。当A的数是2,则有两种情况,B是1或3,如果是1,B在第一分钟会确认,如果B没确认,则B是3。所以假设当A为k时,A会在第k分钟推理出B的数字,则当A=k+1时,如果第k分钟B没有动静,则可以判断B的数不是k,而是k+2,所以在下一分钟即k+1分钟时A推理出数字,结论成立。

更多相关阅读

最新发布的文章