作者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/cn.aspx?n=bbs/Grad-ProbAsk/M.1524842917.A.630.html