I'm reading CLRS, and in Chapter 4 it states that if you guess the asymptotic complexity of a recurrence correctly but cannot quite get the mathematical induction work out, a common method to employ is to subtract some lower-order term from your original guess.
To me this makes sense and my interpretation is as follows; by subtracting a lower-order term (let's say $d$) from your original guess, so long as your recurrence contains more than one sub-problem you will have more than $1$ negative lower-order term propagated, making the answer $\leq$ your original guess given $d$ is of a high enough value.
The example the book gives is as follows:
$$ T(n) = T(\lfloor \frac{n}{2} \rfloor) + T(\lceil \frac{n}{2} \rceil) + 1 $$
Where a reasonable asymptotic complexity guess would be $T(n) = O(n)$ suggesting that $T(n) \leq cn$ for some $n \geq n_0$.
Speeding ahead, we can show that with our current guess:
$$ T(n) = c\lfloor \frac{n}{2} \rfloor + c\lceil \frac{n}{2} \rceil + 1 = cn + 1 \nleq cn \quad \forall \,\,c >0$$
The book then follows it's advice by subtracting some lower-order term from our original guess:
$$ T(n) \leq cn \Rightarrow T(n) \leq cn - d \text{ where } d \geq 0$$
Thus yielding:
$$ T(n) = (c\lfloor \frac{n}{2} \rfloor - d) + (c\lceil \frac{n}{2} \rceil - d) + 1 = cn -2d + 1 \quad \forall \,\,c >0$$
Which gives us the propagating lower-order terms as required in this instance:
$$ T(n) = cn - 2d + 1 \leq cn - d \quad \forall \,\,c >0 $$
One problem I have with what the book demonstrates (on page 85) is their requirement for $d \geq 0$ which to me is a complete undermining of everything they're trying to accomplish. By allowing the case where $d = 0$ you put yourself right back in the place where you started, where instead you need $-2d$ to overpower $1$ so that the inequality actually works. This, as well as realizing you must get the left side's lower-order terms to sum to $< -d$ means we should obviously be restricting $d \geq 1$ not $0$.
Is my logic wrong here, or is the book actually incorrect?
Edit: Picture from book
