algorithm - Case-1 的主定理证明：这些步骤是如何从数学上推导出来的？

Question

我正在阅读 Thomas H. Cormen 的书以理解 Master theorem 的证明。但是，我坚持证明 case-1。请通过更简单的数学推导来帮助我理解数学证明：

谢谢

Answer 1

对于第一个问题：

b^{\log_b(a)} = a

（我们在 SO 中没有 TeX 吗？）

这是因为底数的对数b是 的倒数b^。那么a / a = 1，因此只剩下b^epsilon。

第二个和第三个问题：这是几何级数，你可以在这里找到它：https
: //en.wikipedia.org/wiki/Geometric_series#Formula 为此，和数b^epsilon必须介于零和一（不包括）之间，即|b^epsilon| < 1.