作者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/m.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