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?
Solving recurrences by substitution method: why can I introduce new constants?
algorithm analysis;proof techniques;recurrence relation
I am guessing that the book wants you to proof the stronger hypothesis $T(n) \leq c\log( n -d)$ which implies $T(n) \leq c log(n)$ is also true ( because $n \geq n -d$ for $d\geq 0$. )