[理工] [離散]-數學歸納法 郵票問題
設有面額3元與5元的郵票兩種，證明可用這兩種郵票貼足所有8元與8元以上的郵資。
(黃子嘉老師課本1-31)
解：
利用強數學歸納法：
n=8時， 8=3+5 成立
n=9時， 9=3+3+3 成立
n=10時，10=5+5 成立
假設：n<=k時命題成立，接著考慮n=k+1
因為k-2<=k，根據數學歸納假設，k-2可以用3元郵票及5元郵票貼足，
再加上一張3元郵票即可貼足k+1元郵資，得證。
問題一:
目前對於k-2<=k的解釋為：因為現在考慮n=k+1的情況，
所以接下來才會變成(k+1)-3＝k-2，不曉得這樣解釋是否合理？
Prove that with 3-dollar and 5-dollar stamps，we can make any amount of
postage except 1，2，4 and 7 dollars。(黃子嘉老師課本1-39)
解：
利用強數學歸納證明除了1，2，4，7元郵資以外的任意n元郵資皆可用3元及5元郵資
組合成，這裡需要證明的歸納基礎為n=3，5，6，10(而不是3，5，6，8)
n=3時， 3=3 成立
n=5時， 5=5 成立
n=6時， 6=3+3 成立
n=10時，10=5+5 成立
假設n<k時命題成立，接著考慮n=k
因為k-3<k，根據數學歸納假設，k-3元郵資可用3元及5元郵票組合成，再加上一張3元
郵票即組合成k元郵資，所以n=k時亦成立，得證。
問題二：
想請問為什麼n=3，5，6，10？
目前覺得就上面那一題來看，可以清楚知道用8，9，10可以推到後面n=k+1
所以認為這題使用3，5，6可以推到8和10，因此只需證三項n=3，5，6即可
不曉得在觀念上哪裡有問題。
問題三：
在黃子嘉老師課本1-32下面注意事項有提到：
需證幾項，則要看後面的歸納步驟的證法來決定
想請問這句話的意思，從上面題目還是無法理解。
感謝各位耐心看完問題，謝謝。
※ 編輯: numin 來自: 123.193.240.193 (07/09 19:02)
推
07/09 22:29, , 1F
07/09 22:29, 1F
→
07/09 22:30, , 2F
07/09 22:30, 2F
→
07/09 22:31, , 3F
07/09 22:31, 3F
→
07/09 23:11, , 4F
07/09 23:11, 4F
→
07/09 23:11, , 5F
07/09 23:11, 5F
討論串 (同標題文章)
完整討論串 (本文為第 1 之 3 篇)：