替换法, 解递归方程遇到问题.

Question

我的递归推导:

aT(n/b)+f(n)
a(aT(n/b^2)+f(n/b))+f(n)
...

设存在 i 使 b^i=n, 即 i=logb(n), 则重复上述步骤得:

a^(logb(n))T(1)+a^(logb(n)-1)f(b)+...+af(b^(n-1))+f(b^n)

而正确结果是:

n^(logb(a))[T(1)+u(n)], 其中u(n)=∑(1到i)h(b^i), 其中h(n)=f(n)/n^(logb(a))

---

ps: 我写的公式中默认 ^ 优先级比 / 高 && u(n) 是个求和式.

明显:我的推导和答案,有差别.

我就特别奇怪两点:

1. 答案是怎么引入 n(logb(a)) 的?? 明明推导中是 a 的次方.

2. 答案为什么只含 f(n), 替换的过程中 n 是不断被换的呀?

可能存在某个替换技巧我没有使用.