关于主定理的推导

f(n)=a*f(n/b) + g(n)

f(n) 的结果在算法导论里面有很长的一段证明，作者可能照顾到一些没有学过组合数学的同学。然而，如果有组合数学的基础，这个证明非常简单。
只需要做一个变量替换，令 n=b^k，于是上式就变成：
 f(b^k) = a*f(b^(k-1)) + g(b^k) --->
 F(k) = a*F(k-1) + G(k)
 
这就是一个求解一个递归式的通项问题了，详细的我就不说了……