# asymptotics – Constant in Substitution method for recurrence

The solution for solving the following recurrence with the substitution method involves adding the a constant inside the recurrence, which is confusing to me. This is question 4.3-2 in the CLRS textbook.

Show that $$T(n)=T(n/2) + 1$$ is $$O(lgn)$$

The solution states that the guess should be $$T(n) leq clg(n-2)$$. I understand the need to add the n-2 for the proof. What I don’t understand is the first step in the algebra.

Breakdown:

$$(Tn) leq clg(n/2 + 1 – 2) + 1$$ ( Don’t understand why 1 is added inside the parenthesis.)

$$leq clg((n-2)/2) + 1$$

$$= clg(n-2) – clg2 + 1$$

$$leq clg(n – 2)$$

What I don’t understand is step 1 of the breakdown. Why is there a 1 added to n/2? It might be something minor in the math that I’m missing but I can’t seem to understand it. My only guess is that it is added in the recurrence to match the + 1 at the end of the equation.