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.
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
Get help from others!
Recent Answers
Recent Questions
© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP