[理工] [離散]-數學歸納法 郵票問題

[numin (numin)]

設有面額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)
推 Numbstu:簡單回答你的2.3  就是你初始證明的地方 後來有沒有辦法去
→ Numbstu:證明你後來欲證的K
→ Numbstu:                                                   /拿
→ numin:感謝N大的回答。
→ numin:我大概知道需證幾項及看後面的歸納步驟的意思了。 謝謝