作者JKLee (J.K.Lee)
看板Grad-ProbAsk
標題Re: [理工] 離散 歸納法詢問
時間Fri Apr 27 23:28:35 2018
※ 引述《peterlin495 (夜夜)》之銘言：
: 題目是 2^n >n^3 for all n >= 10
: 裡面最後關鍵的地方 那個 1+1/10的地方是怎麼得出的，想了好久還是不知道，麻煩各位解釋一下，感恩
: http://i.imgur.com/zHTpZsz.jpg
: -----
以數學歸納法證明 P(n) > Q(n) 時，
可以用加法與乘法拆開 P(k+1) 與 Q(k+1)。
然後再看哪一種拆法較方便推出想要的結果。
1.用加法拆:
P(k+1) = P(k) + A
Q(k+1) = Q(k) + B
因 induction hypothesis 得 P(k) > Q(k)
接著試著推導出 A > B
若成功推導出 A > B ，這題就完成了
2.用乘法拆
P(k+1) = P(k) * C
Q(k+1) = Q(k) * D
因 induction hypothesis 得 P(k) > Q(k)
若成功推導出 C > D ，這題就完成了
以你提供的題目為例，用乘法拆開來
2^(k+1) = 2^k * 2
(k+1)^3 = k^3 * [(k+1)/k]^3
因 induction hypothesis 得 2^k > k^3
接著試著推導出 2 > [(k+1)/k]^3
觀察發現 [(k+1)/k]^3 = [1 + 1/k]^3 是遞減函數
代 k=10 可得 2 > [(k+1)/k]^3
所以 k >= 10 時，2 > [(k+1)/k]^3
...後略
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 111.248.68.79
※ 文章網址: https://webptt.com/m.aspx?n=bbs/Grad-ProbAsk/M.1524842917.A.630.html