I'm trying to understand some details about the substitution method for solving recurrences. I'm using the Cormen et al book and there is a chapter of it available [here][1]
At the section 4.1, the following is shown:
$ T(n) ≤ 2(c \frac{n}{2} lg (\frac{n}{2})) + n$
$≤cn lg(\frac{n}{2}) + n$
$= cn lg n - cn lg 2 + n$
$= cn lg n - cn + n$
$≤cn lg n,$
My question:
So my question is why does this keep switching from an inequality, to an equality, and back to an inequality? The original recurrence is an inequality, but here it becomes an inequality in the first step, and continues to switch. Why is it allowed to be so loosely defined?