Prove $2^{\lceil \lg (n-1) \rceil} \ge n-1$

Question

The inequality is from "Introduction to algorithm" of CLRS, section 25.1. What I tried so far is to express $n-1 = e^{\ln(n-1)}$; consider the case when $n-1 = 2^m$ for some integer m; assumed for the purpose of contradiction that the opposite is true. Could someone help?

Thanks.

Update: the log in the question is log of base 2, not e.

Answer 1

Note that $2^{\lg(n-1)} = n-1$ for all $n > 1$. (Here, we use the base $2$ logarithm $\lg$ instead of $\ln$, as using the natural logarithm would lead the inequality being false for all sufficiently large $n$. This usage is probably what the problem implied.) Then, since $\lceil x\rceil \geq x$ for all $x$, and $2^{x}$ is an increasing function for all $x$, we have:

$$2^{\lceil\lg(n-1)\rceil}\geq 2^{\lg(n-1)} = n-1\ \blacksquare$$