I am solving an exercise from the book of Cormen et al. (Introduction To Algorithms). The task is:
Show that solution of $T(n) = T(\lceil n/2\rceil) + 1$ is $O(\lg n)$
So, by big-O definition I need to prove that, for some $c$,
$$T(n) \le c\lg n\,.$$
My take on it was: $$\begin{align*} T(n) &\leq c\lg(\lceil n/2\rceil) + 1 \\ &< c\lg(n/2 + 1) + 1 \\ &= c\lg(n+2) - c + 1\,. \end{align*}$$ As this doesn't seem satisfactory I looked up a solution and the author after getting to the same stage as me decided to introduce a new arbitrary constant $d$: $$\begin{align*} T(n) &\le c\lg(\lceil n/2-d\rceil) + 1 \\ &< c\lg(n/2+1-d) + 1 \\ &< c\lg((n-2d+2)/2) + 1 \\ &= c\lg(n-2d+2) - c + 1 \\ &= c\lg(n-d-(d-2)) - c + 1\,. \end{align*}$$
And now, for $d \ge 2$, $c \ge 1$ and $n > d$,
$$c\lg(n-d-(d-2)) - c + 1 \le c\lg(n-d)\,.$$
What I don't understand is how does it prove that $T(n) \le c\lg n$? Cormen et al. make a big point that you have to prove the exact form of the inductive hypothesis which in this case was $T(n) \le c\lg n$. They then go on to show example similar to one above.
How is that the exact form of the inductive hypothesis? This doesn't seem to fit the big-O definition. When can I omit constants or cheat them away? When is it wrong?