Solving recurrences by substitution method: why can I introduce new constants? 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&nbsp;$c$,

$$T(n) \le c\lg n\,.$$

My take on it was:
$$\begin{align*}
    T(n) &amp;\leq c\lg(\lceil n/2\rceil) + 1 \\
         &amp;&lt; c\lg(n/2 + 1) + 1 \\
         &amp;= 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&nbsp;$d$:
$$\begin{align*}
    T(n) &amp;\le c\lg(\lceil n/2-d\rceil) + 1 \\
         &amp;&lt; c\lg(n/2+1-d) + 1 \\
         &amp;&lt; c\lg((n-2d+2)/2) + 1 \\      
         &amp;= c\lg(n-2d+2) - c + 1 \\
         &amp;= c\lg(n-d-(d-2)) - c + 1\,.
\end{align*}$$

And now, for $d \ge 2$, $c \ge 1$ and $n &gt; 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?
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$. )