[離散] 數學歸納法、強數學歸納法的n=1

看板Math作者 (片翼碎夢)時間3年前 (2020/10/27 10:41), 3年前編輯推噓5(5推 0噓 113→)
留言118則, 4人參與, 3年前最新討論串1/2 (看更多)
感覺愈寫反而愈抓不太到數學歸納法對於第一步驟和最後一步驟的要求 像是郵票題目 證明除1、3、4、7外，皆可用3、5元郵票組合成 ＜解法＞ n=3 ：3=3 n=5 ：5=5 n=8 ：8=3+5 n=9 ：9=3+3+3 n=10：10=5+5 設n<k成立，consider n=k n-3小於k成立　加回去變k n-5小於k成立　加回去變k 關於最後這一項，不知道到底該證明幾個n-x的狀況才夠 也不知道第一項到底是不是證明到n=10就足夠 然後另外一個搞不懂的狀況是，馬顏色同一種的延伸題目，如下： 關於蓋金字塔 一粒沙蓋不起來 k粒沙蓋不起來 k+1粒沙蓋不起來 所以人類蓋不出金字塔 改成這樣就不知道怎麼抓邏輯漏洞了 對數學歸納法一直都不是有辦法很信任 假設我看到一個數列都是2，我要怎麼才能知道前方不會有個1？ -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 111.71.214.119 (臺灣) ※ 文章網址: https://www.ptt.cc/bbs/Math/M.1603766473.A.2F3.html ※ 編輯: fragmentwing (111.71.214.119 臺灣), 10/27/2020 10:44:41
→
10/27 11:00, 3年前 , 1F
數學歸納法是關於無限的定理 對他不信任是正常的
10/27 11:00, 1F
推
10/27 11:00, 3年前 , 2F
蓋金字塔的問題是，你要先定義清楚什麼叫做金字塔，
10/27 11:00, 2F
→
10/27 11:00, 3年前 , 3F
五粒沙疊成類似四面體的形狀可以是金字塔嗎？沒有明
10/27 11:00, 3F
→
10/27 11:00, 3年前 , 4F
確金字塔的定義，你要怎麼證明k+1粒沙蓋不成？
10/27 11:00, 4F
→
10/27 11:01, 3年前 , 5F
但使用數學歸納法時你永遠要確保兩件事 第一件事是
10/27 11:01, 5F
→
10/27 11:02, 3年前 , 6F
起點是存在的 第二件事是鏈鎖是一定會發生的
10/27 11:02, 6F
→
10/27 11:02, 3年前 , 7F
關於蓋金字塔 你並沒有保證鏈鎖一定會發生 也就是
10/27 11:02, 7F
→
10/27 11:03, 3年前 , 8F
另外你看到數列都是2，不知道前項，所以你沒有起始
10/27 11:03, 8F
→
10/27 11:03, 3年前 , 9F
條件（或者起始條件只能從2開始），另外你也沒辦法
10/27 11:03, 9F
→
10/27 11:03, 3年前 , 10F
證明2的下一項一定是2，所以數學歸納法本來就沒辦法
10/27 11:03, 10F
→
10/27 11:03, 3年前 , 11F
用在這個問題上。
10/27 11:03, 11F
→
10/27 11:03, 3年前 , 12F
你沒有正當的理由說明P(k)發生時 P(k+1)是無法發生
10/27 11:03, 12F
說到這個 其實馬的題目也能這樣證吧 但不知道為什麼 看大家的解法都是用無法重疊去破解
→
10/27 11:04, 3年前 , 13F
或一定發生的
10/27 11:04, 13F
※ 編輯: fragmentwing (111.71.214.119 臺灣), 10/27/2020 11:05:28
→
10/27 11:06, 3年前 , 14F
看到一個數列前頭都是2 你沒有任何理由保證鏈鎖一定
10/27 11:06, 14F
→
10/27 11:07, 3年前 , 15F
會發生 自然就不知道下一個是什麼
10/27 11:07, 15F
→
10/27 11:08, 3年前 , 16F
馬的題目是什麼??
10/27 11:08, 16F
任n匹馬具相同顏色 n=1成立 設n＝k成立 考慮n=k+1 然後就會講到overlap、重疊之類的
→
10/27 11:11, 3年前 , 17F
另外郵票題目是可以3x+5y=n n>=8 一定有正整數解去
10/27 11:11, 17F
→
10/27 11:12, 3年前 , 18F
看的 用數論的方法就能解釋 雖然文中數學歸納法是正
10/27 11:12, 18F
→
10/27 11:13, 3年前 , 19F
確的 但如果你不放心 你可以用其他方法證
10/27 11:13, 19F
可是關於最後一步驟 如果今天題目寫1，2，3，4以外皆可由5元郵票組成 那最後一步驟時寫一個k-5可組成k就成了? ※ 編輯: fragmentwing (111.71.214.119 臺灣), 10/27/2020 11:14:34
→
10/27 11:15, 3年前 , 20F
喔喔 我知道馬的問題了 馬的問題是在你沒有確保鏈鎖
10/27 11:15, 20F
※ 編輯: fragmentwing (111.71.214.119 臺灣), 10/27/2020 11:16:21
→
10/27 11:16, 3年前 , 21F
一定發生 也就是P(k) implies P(k+1)這件事對所有的
10/27 11:16, 21F
→
10/27 11:17, 3年前 , 22F
k都會成立 因為論述中不能適用在k=1的情況
10/27 11:17, 22F
→
10/27 11:19, 3年前 , 23F
我不太懂overlap是指什麼 馬的問題缺失是在P(1)推不
10/27 11:19, 23F
「因為在證兩匹馬時，前半後半個1，沒有overlap」只有在n大於等於3時有overlap之情形，所以無法用p(1)來證得p(2)
→
10/27 11:19, 3年前 , 24F
到P(2)
10/27 11:19, 24F
→
10/27 11:20, 3年前 , 25F
"可是關於最後一步驟...">>>可是你沒有確保起點存在
10/27 11:20, 25F
→
10/27 11:21, 3年前 , 26F
呀 數學歸納法中"起點存在"和"鏈鎖一定發生"是同樣
10/27 11:21, 26F
所以我才會想起點的狀況要列到什麼程度才夠 ※ 編輯: fragmentwing (111.71.214.119 臺灣), 10/27/2020 11:21:56
→
10/27 11:22, 3年前 , 27F
重要的 有些書寫證明會省略這個或那個 是因為有時他
10/27 11:22, 27F
※ 編輯: fragmentwing (111.71.214.119 臺灣), 10/27/2020 11:23:15
→
10/27 11:23, 3年前 , 28F
是顯然的 不是因為他不用check
10/27 11:23, 28F
→
10/27 11:25, 3年前 , 29F
例到最小的k-3或k-5會存在就好了
10/27 11:25, 29F
→
10/27 11:28, 3年前 , 30F
如果真的無法理解 那就列8,9,10 然後分別考慮3k,
10/27 11:28, 30F
→
10/27 11:29, 3年前 , 31F
3k+1,3k+2的情況就好了 不用特別去想k-3或k-5
10/27 11:29, 31F
還有 47 則推文
還有 3 段內文
→
10/27 13:25, 3年前 , 79F
P(n+1)"這件事是對的違反直覺的 至於把起點改為2 也
10/27 13:25, 79F
→
10/27 13:26, 3年前 , 80F
是不能用數學歸納法 因為沒有保證起點是對的
10/27 13:26, 80F
→
10/27 14:34, 3年前 , 81F
我誤會了 "若任兩匹馬顏色一樣 則所有馬顏色一樣"已
10/27 14:34, 81F
→
10/27 14:35, 3年前 , 82F
經和原本馬問題無關了 實際上也不需要用數學歸納法
10/27 14:35, 82F
→
10/27 14:35, 3年前 , 83F
去證明
10/27 14:35, 83F
推
10/27 16:50, 3年前 , 84F
並沒有無關喔, 後一問題是原問題改變 base case
10/27 16:50, 84F
→
10/27 16:51, 3年前 , 85F
後一問題能用原論證證明表示原論證本來就無誤
10/27 16:51, 85F
→
10/27 16:51, 3年前 , 86F
問題完全只在 P(1)→P(2) 無法用原論證證明
10/27 16:51, 86F
→
10/27 16:52, 3年前 , 87F
但就因為這一個無法證明使得結論變為荒謬
10/27 16:52, 87F
→
10/27 17:34, 3年前 , 88F
原本問題是"對於任意n匹馬 這n匹馬顏色都相同"
10/27 17:34, 88F
→
10/27 17:34, 3年前 , 89F
形式是" for all x1,x2,...xn, Q(x1,x2,...,xn)"
10/27 17:34, 89F
→
10/27 17:34, 3年前 , 90F
改過的問題是"對於任意n匹馬 若任意兩兩顏色相同 則
10/27 17:34, 90F
→
10/27 17:34, 3年前 , 91F
這n匹馬顏色相同"
10/27 17:34, 91F
→
10/27 17:34, 3年前 , 92F
形式是 "for all x1,x2,...,xn, if for all i,j A(x
10/27 17:34, 92F
→
10/27 17:34, 3年前 , 93F
i,xj), then Q(x1,x2,....,xn)"
10/27 17:34, 93F
→
10/27 17:34, 3年前 , 94F
第2個問題只要固定其中一匹馬 大家都跟這匹馬相比即
10/27 17:34, 94F
→
10/27 17:34, 3年前 , 95F
可
10/27 17:34, 95F
→
10/27 17:34, 3年前 , 96F
就算硬要用數學歸納法證 兩者的induction hypothesi
10/27 17:34, 96F
→
10/27 17:34, 3年前 , 97F
s也不同
10/27 17:34, 97F
→
10/27 17:34, 3年前 , 98F
第一個P(n):對於任意n匹馬 這n匹馬顏色都相同
10/27 17:34, 98F
→
10/27 17:34, 3年前 , 99F
P(n)推P(n+1):若"任意n匹馬 這n匹馬顏色都相同" 則
10/27 17:34, 99F
→
10/27 17:34, 3年前 , 100F
"任意n+1匹馬 這n+1匹馬顏色都相同"
10/27 17:34, 100F
→
10/27 17:34, 3年前 , 101F
第二個P(n):對於任意n匹馬 若任意兩兩顏色相同 則這
10/27 17:34, 101F
→
10/27 17:34, 3年前 , 102F
n匹馬顏色相同
10/27 17:34, 102F
→
10/27 17:34, 3年前 , 103F
P(n)推P(n+1):若"對於任意n匹馬 若任意兩兩顏色相同
10/27 17:34, 103F
→
10/27 17:34, 3年前 , 104F
則這n匹馬顏色相同" 則 "對於任意n+1匹馬 若任意
10/27 17:34, 104F
→
10/27 17:34, 3年前 , 105F
兩兩顏色相同 則這n+1匹馬顏色相同"
10/27 17:34, 105F
→
10/27 17:34, 3年前 , 106F
用到的假設和要證的東西已經不同了 你說用類似的想
10/27 17:34, 106F
→
10/27 17:34, 3年前 , 107F
法證ok 但直接用原論證一定是不行的
10/27 17:34, 107F
→
10/27 17:34, 3年前 , 108F
最簡單的看法就是 從n+1匹馬選出n匹馬後 在第一個
10/27 17:34, 108F
→
10/27 17:34, 3年前 , 109F
情況 這n匹馬就是同顏色的 但在第二個情況 你必須
10/27 17:34, 109F
→
10/27 17:34, 3年前 , 110F
先check任意兩兩相同顏色 才能下結論這n匹馬同顏色
10/27 17:34, 110F
→
10/27 17:34, 3年前 , 111F
兩者推到選出來的n匹馬同顏色的方式不同
10/27 17:34, 111F
→
10/27 17:39, 3年前 , 112F
荒謬的是"對於任意n匹馬 這n匹馬顏色必然相同"
10/27 17:39, 112F
→
10/27 17:39, 3年前 , 113F
"對於任意n匹馬 若兩兩顏色相同 則這n匹馬顏色必然
10/27 17:39, 113F
→
10/27 17:39, 3年前 , 114F
相同"則完全沒問題
10/27 17:39, 114F
→
10/27 17:45, 3年前 , 115F
兩個問題形式已經不同 說是相關勉強可以 但並不是
10/27 17:45, 115F
→
10/27 17:45, 3年前 , 116F
誰基於誰 我認為無關 就是他們形式上已經無關 前者
10/27 17:45, 116F
→
10/27 17:45, 3年前 , 117F
有問題的證明 也沒辦法直接給後者用(實際上也不需要
10/27 17:45, 117F
→
10/27 17:45, 3年前 , 118F
)
10/27 17:45, 118F
‣ 更多 fragmentwing 的文章
文章代碼(AID): #1VbuZ9Bp (Math)
‣ 更多 fragmentwing 的文章
文章代碼(AID): #1VbuZ9Bp (Math)