Re: [其他] 數學歸納法證明

[Eliphalet (系統過宅)]

※ 引述《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
推 Rachelmas   : 感謝熱心回答！ 不過我有幾個問題想問
→ Rachelmas   : 1.為什麼第二解裡 求出來n要大於6.多 最後n=6卻其實
→ Rachelmas   : 也可？是推導裡哪裏產生不嚴謹了嗎？
 原來是原PO，難怪總覺得哪裡怪怪的

 怎麼會問我推導有沒有不嚴謹呢(要是有的話，這是我寫的，我怎麼會知道？ XD)

 而且這樣問有點不太禮貌吧(要嘛你就直接指出來)

→ Rachelmas   : 2.怎麼知道算幾要用(n-2)! 而不用(n-1)!之類的？
→ Rachelmas   : （有求過 的確不行 但不知道是怎麼想到要用(n-2)!）

 1. 這只是非 sharp 的情況罷了，但也算靠近 6 啊

 2. 然後用 (n-2)! 只是為了方便湊 (n/2)，這樣比較好處理且好計算

    要 (n-1)! 也行啊，但是樣子有點髒。如果用類似的方法的話

    好像 n 從 9 之後吧

 3. 指數的增加效果比底數兇
※ 編輯: Eliphalet (114.46.214.201), 02/12/2016 12:01:33
推 Rachelmas   : 啊啊啊真抱歉 用詞遣詞不太嚴謹 我沒有惡意....我
→ Rachelmas   : 的意思是 是不是哪裡應該tight bound而為了方便用lo
→ Rachelmas   : ose bound之類的 所以最後還要做邊界檢查 不是指推
→ Rachelmas   : 導有錯QQ sorry~
推 Rachelmas   : 然後我資質比較駑鈍 所以看不出來哪邊可以合理解釋
→ Rachelmas   :  故煩請指教
→ Rachelmas   : 後面的解釋有懂了 再次感謝~
  抱歉，我也沒有惡意

  其實我沒想那麼多，盡量靠近 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