TransWikia.com

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

Mathematics Asked by Hiep on February 12, 2021

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.

One Answer

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 xrceil geq x$ for all $x$, and $2^{x}$ is an increasing function for all $x$, we have:

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

Answered by Joshua Wang on February 12, 2021

Add your own answers!

Ask a Question

Get help from others!

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP