Re: [其他] 數學歸納法證明
※ 引述《Rachelmas (Rachelmas)》之銘言：
: 一題跟computer science有關的數學證明題
: 用數學歸納法證明：
: n! < (n^n)/(2^n) for n>=6
: 我只解了基本的步驟：
: Base case:
: 6!<6^6/2^6 OK
: Induction step:
: Assume n=k, k!<k^k/2^k
: For n=k+1, (k+1)!=(k+1)k!
: <(k+1)k^k/2^k -- (a)
: <=(k+1)(k+1)^k/(2*2^k) -- (b) //從不等式右邊拆出來的
: 但要從(a)導到(b)必須證明k^k<=(k+1)^k/2
: 於是乎我就卡住了...
: 不知道方向對不對？
: 煩請各位指點迷津 感激不盡<(_ _)>
: p.s.題目最後還希望證明(n^n)/(3^n) < n! < (n^n)/(2^n)
是啊題目規定Orz
可以請教其他方法大概是怎麼跑嗎?
※ 編輯: Rachelmas (147.8.169.204), 02/11/2016 11:27:44
這裡用其他方法，至於好不好就就見仁見智了
不等式有兩個部分
1. (n/3)^n < n!
取自然對數後，這等價於
n log(n) - n log(3) < log(2) + log(3) + ... + log(n)
n
從面積的關係來看，RHS > ∫ log(x) dx = n log(n) - n + 1
1
> n log(n) - n log(3)
所以這個不等式對所有自然數 n 都成立
2. n! < (n/2)^n ， n≧6
從算幾不等式可知，
((n-2)!)^(1/(n-3)) < (n/2) ，故 (n-2)! < (n/2)^(n-3)
因此只要 n*(n-1) < (n/2)^3 ， 亦即 n > 2(2+√2) ≒ 6.828
且 n 不等於 1，則有 n! < (n/2)^n
好吧，取的不太好，所以 n = 6 以下用手工驗證
6! = 720 ， 3^6 = 729 ， 可
5! = 120 ， 2.5^5 = 97.65625 ， 不可
4! = 24 ， 2^4 = 16 ， 不可
3! = 6 ， 1.5^3 = 3.375 ， 不可
2! = 2 ， 1^2 = 1 ， 不可
1! = 1 ， 0.5^1 = 0.5 ， 不可
所以這個不等式從 n = 6 開始成立
(如果只是要證明你的題目，驗證 n = 6 就好 :P)
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.46.214.201
※ 文章網址: https://www.ptt.cc/bbs/Math/M.1455182759.A.271.html
推
02/12 10:30, , 1F
02/12 10:30, 1F
→
02/12 10:30, , 2F
02/12 10:30, 2F
→
02/12 10:31, , 3F
02/12 10:31, 3F
原來是原PO，難怪總覺得哪裡怪怪的
怎麼會問我推導有沒有不嚴謹呢(要是有的話，這是我寫的，我怎麼會知道？ XD)
而且這樣問有點不太禮貌吧(要嘛你就直接指出來)
→
02/12 10:32, , 4F
02/12 10:32, 4F
→
02/12 10:32, , 5F
02/12 10:32, 5F
1. 這只是非 sharp 的情況罷了，但也算靠近 6 啊
2. 然後用 (n-2)! 只是為了方便湊 (n/2)，這樣比較好處理且好計算
要 (n-1)! 也行啊，但是樣子有點髒。如果用類似的方法的話
好像 n 從 9 之後吧
3. 指數的增加效果比底數兇
※ 編輯: Eliphalet (114.46.214.201), 02/12/2016 12:01:33
推
02/12 12:09, , 6F
02/12 12:09, 6F
→
02/12 12:09, , 7F
02/12 12:09, 7F
→
02/12 12:09, , 8F
02/12 12:09, 8F
→
02/12 12:09, , 9F
02/12 12:09, 9F
推
02/12 12:12, , 10F
02/12 12:12, 10F
→
02/12 12:12, , 11F
02/12 12:12, 11F
→
02/12 12:14, , 12F
02/12 12:14, 12F
抱歉，我也沒有惡意
其實我沒想那麼多，盡量靠近 6 就是了
如果你不計較計算繁瑣的話，用類似上面的方法
但乘的範圍從 3 到 (n-3)，這時可以算出只要
n > 2 (sqrt(3) + sqrt(5-2sqrt(3))) ≒ 5.943
(不特別計較的話，計算機代數字算就好，或許不用真的算出來)
不等式成立。但不論如何，我這樣只能證明多少以後
不等式會成立，在此之前的 n = 1 到 5，還是要人工驗證
當然你題目沒要求這個就是了
※ 編輯: Eliphalet (114.46.214.201), 02/12/2016 12:46:07
討論串 (同標題文章)