作者LPH66 (1597463007)
看板Math
标题Re: [中学] 强归纳法
时间Wed Sep 24 14:58:20 2014
: → Arton0306 : 但C(N,N)题目有写了，虽然我觉得题目双重定义怪怪的 09/24 00:46
: → Arton0306 : 比较困扰的是这个证明架构 用了很强的假设 09/24 00:49
: 推 LPH66 : 关於你这个问题, 数学归纳法有所谓的「强形式」 09/24 02:39
: → LPH66 : 一般的归纳法是「P(n-1)→P(n)」 09/24 02:40
: → LPH66 : 强形式是「P(0)且P(1)且...且P(n-1)→P(n)」 09/24 02:40
: → LPH66 : 只要确定到你时前面的真的都成立那就行了 09/24 02:40
: → LPH66 : 其他都是一样的 09/24 02:41
: 推 LPH66 : 事实上, 适当改写问题即可将强形式转为一般形式: 09/24 02:58
: → LPH66 : 令 Q(n) 为「P(0)且P(1)且...且P(n)」 09/24 02:58
: → LPH66 : 那强形式的推导就能写成「Q(n-1)→Q(n)」 09/24 02:59
: → LPH66 : 以你的例子来说, (B)部份的结论可以再多走一步 09/24 03:00
: → LPH66 : 把前提跟结论合起来就能得到下一次的前提了 09/24 03:00
: → LPH66 : 这即是我上面写的 Q(n) 09/24 03:01
: → Arton0306 : L大可以回文吗XD 看不是很懂 要怎麽证才会都用到前 09/24 13:56
: → Arton0306 : 面已经确定成立的 09/24 13:56
其实有的时候对证明来说能用不只前一个结果会让证明好写很多
举个最经典的: 费氏数列通式的证明
由於已知的是这一项跟前两项有关系
所以在这里使用强型式的归纳法证明会比较好写
(虽然在这两个例子里都只用到前面一两个而已)
而两个型式的归纳法其实是一样的, 因为两者的差别只在於那个 n=k 跟 n≦k 而已
形式上虽然如我推文所说的可以如此改写
但对实际证明来说, 就算这样改写最後出来的证明其实差不多
可以比较以下两段:
(一些证明) P(0), P(1), ... P(B) 皆成立。
若 P(n) 对 n≦k 成立，
则 (一些跟 P(k)、P(k-1)、... 有关的推理)
故 P(k+1) 成立。
由(强型式)数学归纳法得 P(n) 对自然数 n 成立。
=====================================================
令 Q(n) 表示 P(0), P(1), ... P(n) 皆成立。
(一些证明) Q(B) 成立。
若 Q(n) 对 n = k 成立，
则 P(k)、P(k-1)、... 成立，(一些跟 P(k)、P(k-1)、... 有关的推理)
故 P(k+1) 成立；跟 Q(k) 成立合起来证得 Q(k+1) 成立。
由(普通)数学归纳法得 Q(n) 对自然数 n≧B 成立；於是 P(n) 对自然数 n 成立。
可以看到其实最後的证明除了一些跟 P Q 有关的细节之外都是一样的
所以这种强型式的归纳法就放心用吧
题目做多了就知道条件越多能用的材料就越多, 也会比较好做
--
'Oh, Harry, don't you
see?' Hermione breathed. 'If she could have done
one thing to make
absolutely sure that every single person in this school
will read your interview, it was
banning it!'
---'Harry Potter and the order of the phoenix', P513
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 140.112.30.46
※ 文章网址: http://webptt.com/cn.aspx?n=bbs/Math/M.1411541902.A.905.html
※ 编辑: LPH66 (140.112.30.46), 09/24/2014 14:59:48
1F：推 Arton0306 : 感谢L大 再问一个问题 有没有可能发生一个情况 09/25 00:25
2F：→ Arton0306 : 我用了一个错误的假设，却证明出P(k+1)也成立了 09/25 00:25
3F：推 Arton0306 : 不能"用一个错误的假设 证出P(k+1)"应该也要证明@@ 09/25 00:36
你这个问题可以用一个着名的例子来说明: 「所有马都是同色」的「证明」
这个「证明」是这样的:
一只马当然同色
现在假设任何 N≦K 只马都是同色
将 K+1 只马它们编号 1 ~ K+1
那麽 1~K 一共 K 只马同色, 2~K+1 这 K 只马也同色
它们有共同的 2~K 这些马, 所以这 K+1 只马也是同色
这个「证明」的错误在於「共同的 2~K 这些马」这句话只在 K≧2 成立
所以这个归纳要成立基础要证到 2 才行
但就是这个 N=2 的状况不成立, 所以整个推理也就不对了
※ 编辑: LPH66 (123.195.39.85), 09/25/2014 00:46:37
4F：推 Arton0306 : 这例子我知道 拿掉某一只马x 和另一只马y 剩下的集 09/25 00:45
5F：→ Arton0306 : 合不一定有交集 所以P(k)=>P(k+1)无法证明 09/25 00:47
6F：→ Arton0306 : 等等喔 我没看到修文XD 09/25 00:48
7F：→ LPH66 : 因为要讲的有点多所以直接修文XD 09/25 00:48
8F：推 Arton0306 : 这个例子我认为是 2~K可能为空集合 所以在inductive 09/25 00:54
9F：→ Arton0306 : 阶段错误 是一个"假设错误 也无法证出P(k+1)"的例子 09/25 00:54
10F：→ Arton0306 : 但万一有 假设错 最後证出来怎麽办xd 虽然我找不到 09/25 00:56
11F：→ LPH66 : 换个方式思考这个例子, 它的推论在 K≧2 时确实成立 09/25 01:06
12F：→ LPH66 : 所以 K=2 的状况就是你所谓「假设错但最後证出来」 09/25 01:06
13F：→ LPH66 : 这里的「假设错」就是 N=2 不成立这件事 09/25 01:07
14F：→ LPH66 : 你可以想像一个平行世界, 那里任两只马都确实同色 09/25 01:07
15F：→ LPH66 : 这样根据这个推论我们就能得到那世界的所有马都同色 09/25 01:08
16F：推 Arton0306 : 我记得以前修离散的时候考过一个题目 09/26 22:14
17F：→ Arton0306 : 也是要找数学归纳法中证明的错误 题型记得跟 09/26 22:15
18F：→ Arton0306 : min(x,y)有关 最後完成一个很神奇(是错的)的结论 09/26 22:15
19F：→ Arton0306 : 不知道有没有人知道题目 (希望有人看到这一篇) 09/26 22:16