推 bernachom:謝謝您的幫忙，寫得很清楚^^ 11/01 12:50
※ 引述《bernachom (Terry)》之銘言：
: 請教一下
: 考慮在一個費氏數列下
: 初值為F0=0, F1=1
: T(n)>n/2^2
: =========
: 這樣子要怎麼歸呢?
: 歸了很久...感覺沒歸到什麼，麻煩教導了
: 謝謝..
初值的F0跟F1是指T(0)跟T(1)嗎
如果是的話
這個T(n)>(n/2)^2要在n>6以後才會成立
induction on n
n小於等於8的狀況分別為:
T(0) = 0 = (0/2)^2 非大於,不成立
T(1) = 1 > (1/2)^2 成立
T(2) = 1 = (2/2)^2 非大於,不成立
T(3) = 2 < (3/2)^2 不成立
T(4) = 3 < (4/2)^2 不成立
T(5) = 5 < (5/2)^2 不成立
T(6) = 8 < (6/2)^2 不成立
T(7) = 13> (7/2)^2 成立
T(8) = 21> (8/2)^2 成立
設當n=k-2及n=k-1時成立, 即T(k-2)>[(k-2)/2]^2 , T(k-1)>[(k-1)/2]^2
則當n=k時,
T(k)=T(k-1)+T(k-2)
>[(k-2)/2]^2+[(k-1)/2]^2
k^2-4k+4 k^2-2k+1
= ---------- + ----------
4 4
2k^2-6k+5
= -----------
4
又當k>6時, k^2>6k
2k^2-6k+5 k^2+5 k^2
=>當k>6時, T(k)> ----------- > --------- > ----- = (k/2)^2 成立
4 4 4
∴由數學歸納法可知,當n>6時,T(n)>(n/2)^2 #
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.113.139.83