[理工] 離散 解遞迴

[a866662 (seal)]

http://imgur.com/a/fHiYd
大家好  我想請問這題的第二小題
因為他的參數有上界跟下界
如果可以忽略的話就能直接用老大定律
但我證不出來能不能忽略
如果不能忽略就不知道怎麼解了
想請問大家怎麼看這題 感謝

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 1.164.40.100
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1478407860.A.AD5.html
※ 編輯: a866662 (1.164.40.100), 11/06/2016 12:52:36
推 hut326521: 展開帶入？
推 Transfat: 大概估計？
→ ken52011219: 要用Substitution method去做
→ a866662: 我有想過substitution但想不出怎麼代
→ a866662: 能不能麻煩大大稍微提示一下
→ ken52011219: 很長一串 等我一下 QQ
推 ken52011219:  http://i.imgur.com/LaCnofl.jpg
→ ken52011219: 我有點失誤的地方是 d_1^2(lg(d1))那邊我應該直接寫
→ ken52011219: d就好 因為好像不能直接那樣寫
→ a866662: 感謝K大~但證1.2時有用到假設的條件來證這樣可以嗎
→ a866662: 譬如歐妹嘎如果=n^2
→ a866662: 是不是就不能用條件1來證後面的東西
→ ken52011219: 你的意思是拿1的結果證2嗎@@?
→ ken52011219: 不太懂意思 但 假如假設的條件成立了就可以拿來證明
→ a866662: 因為你在證1成立的時候的第一行
→ a866662: 感覺是用1假設的條件 但這時候1還沒成立
→ ken52011219: 可以唷 這是Mathematical induction
→ ken52011219: Substitution Method 有兩個步驟
→ ken52011219: 1. Guess the form of the solution
→ ken52011219: 2. Use Mathematical induction to find the constan
→ ken52011219: -t and show that the solution works 有興趣可以翻
→ ken52011219: 楓葉本的第83頁 有詳細講解關於這部分
→ a866662: 原來如此~ 突然忘記有induction這個東西XD
→ a866662: 感謝K大的講解~