Re: [中學] 強歸納法

看板Math作者LPH66 (1597463007)時間9年前 (2014/09/24 14:58)推噓5(5推 0噓 14→)

留言19則, 2人參與討論串2/3 (看更多)

: → 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://www.ptt.cc/bbs/Math/M.1411541902.A.905.html ※ 編輯: LPH66 (140.112.30.46), 09/24/2014 14:59:48

推