Help with problem 4.1-1 from CLRS 2nd edition
As pointed out in the comments, your proof is wrong since it is not true in general that $\log \lceil n/2 \rceil \leq \log n/2$. For example, if $n = 1$ then the left-hand side is zero while the right-hand side is negative.

In the comment you mention that the text states that they omit floors and ceilings. This is always wrong. You cannot &quot;omit&quot; stuff. It invalidates your entire reasoning. (Sometimes, however, you can use true inequalities to get rid of floors or ceilings: for example, $\lfloor x \rfloor \leq x$.)
Consider for example a divide-and-conquer algorithm which splits its input into two halves and performs some $O(n)$ processing. You often see its running time expressed as the recurrence
$$ T(n) = 2T(n/2) + O(n). $$
This is clearly wrong – what if $n$ is odd? What does $T(13.5)$ even mean? The argument has to be a positive integer! The real recurrence is probably more like
$$
T(n) = T(\lfloor n/2 \rfloor) + T(\lceil n/2 \rceil) + O(n).
$$
When the text states that they omit floors and ceilings, they are being sloppy. They allow themselves to do that since you can solve the true recurrence $T(n) = T(\lfloor n/2 \rfloor) + T(\lceil n/2 \rceil) + O(n)$ via the fake one $T(n) = 2T(n/2) + O(n)$, which should be interpreted as defining a function $T(n)$ for all positive values of $n$.
You can see this sentiment expressed formally in the Akra–Bazzi theorem, where floors and ceilings don't change the answer. Another way to see it is to consider only values of $n$ of the form $n = 2^m$. For these values, the recurrence $T(n) = 2T(n/2) + O(n)$ does hold. You can prove by induction that the solution to the recurrence $T(n) = T(\lfloor n/2 \rfloor) + T(\lceil n/2 \rceil) + O(n)$, and so it suffices (in this case) to determine the asymptotic rate of growth for $n$ of the form $n = 2^m$.

How do you solve your recurrence, $T(n) = T(\lceil n/2 \rceil) + 1$? First of all, you have to supply some base case, say $T(1) = C$. Given $n$, we now construct the following sequence: $n_0 = n$, $n_{i+1} = \lceil n_i/2 \rceil$. You can check that $T(n)$ equals $C$ plus the minimal index $i$ such that $n_i = 1$.
Since $\lceil m/2 \rceil \leq (m+1)/2$, we know that $n_1 \leq (n+1)/2$, and so $n_2 \leq (n+3)/4$, and $n_3 \leq (n+7)/8$, and so on. More generally, $n_i \leq (n+2^i-1)/2^i &lt; n/2^i + 1$. Hence if $i = \lceil \log_2 n \rceil$ then $n_i &lt; n/n + 1 = 2$, implying that $n_i \leq 1$.
In the other direction, clearly $n_i \geq n/2^i$, and so if $i = \lceil \log_2 n \rceil - 1 &lt; \log_2 n$ then $n_i &gt; 1$, implying that $T(n) &gt; \lceil \log_2 n \rceil - 1 + C$.
We conclude that the minimal $i$ such that $n_i = 1$ is exactly $\lceil \log_2 n \rceil$. Hence $T(n) = C + \lceil \log_2 n \rceil$.