复杂性理论中的代入法

Question

请告知是否应将此答案移至数学论坛。

我对我们如何简化复杂性理论方程感到很困惑。

例如，假设我们有这个小斐波那契算法：

---

---

我们得到以下信息：

---

我很难理解的是公式 T(n) 是如何扩展和简化的，尤其是这个：

我在这里真正缺少什么？

谢谢

编辑

这取自第 775 页的 book。

Answer 1

让我重新表述一下声明：

There exist some a and b such that T(n) < aF_n - b

现在开始证明

Chose b large enough to dominate the constant term.

现在最后一个不等式应该清楚了。