我在阅读CLRS书籍以了解如何使用替换方法解决重复问题，并发现以下示例：
Recurrence, T(n) = 2T(n/2) + n
Guess Solution, T(n) = O(nlgn)
Proof that T(n) ≤ cnlgn
我的问题是：
问题1：为什么解方程的符号在不等式和等式符号之间变化？
问题2：我们知道在数学归纳法中，归纳步是下一个值，所以如果当前值是n，那么下一个值应该是（n+1），但是为什么他们用n/2作为下一个归纳步？
请帮我解释一下这个问题。这将有助于我理解替代法。谢谢
最佳答案
问题1：这两个等式只是对前一行的重写，因为log（a/b）=log（a）-log（b）和log（2）=1
问题2：对于归纳步骤，因为我们把t（n）写成t（n/2）的函数，所以一个步骤是直接的2因子。如果递推公式是t（n）=f（t（n-1）），则会有一个1-加法的经典归纳步骤。
还要注意，在这个证明中，假设T（1）可以在恒定时间内完成。