Proof inequality with log

Question

How can I prove that there exist $n_0$, $c$ such that for all $n>n_0$: $$n^{\log_2{n}}\le c2^{n}$$ (So I mean the log of n with base 2). Can anybody help me?

Answer 1

First, let's show that $$ \lim_{n\to\infty}\frac{\log(n)^2/\log(2)}{\log(c)+n\log(2)}=0 $$ Using L'Hospital twice gives $$ \begin{align} \lim_{n\to\infty}\frac{\log(n)^2/\log(2)}{\log(c)+n\log(2)} &=\lim_{n\to\infty}\frac{2\log(n)/n}{\log(2)^2}\\ &=\lim_{n\to\infty}\frac{2\log(n)}{\log(2)^2n}\\ &=\lim_{n\to\infty}\frac{2/n}{\log(2)^2}\\[6pt] &=0 \end{align} $$ Thus, there is an $n_0$ so that for $n\ge n_0$ $$ \frac{\log(n)^2/\log(2)}{\log(c)+n\log(2)}\le1 $$ Thus, $$ \log(n)^2/\log(2)\le\log(c)+n\log(2) $$ and therefore, $$ n^{\log_2(n)}\le c\,2^n $$

Answer 2

We know that $\log n \leq \sqrt{n}$ for all $n > 0$. Hence, that $\log n \leq \sqrt{n + \log_2 k}$ for each $k \geq 1$ and all $n > 0$. If you don't know this, it is easy to demonstrate using the methods of calculus ($e$.$g$., look at the limit of the quotient of $\log n$ and $\sqrt{n}$ or approximate $\log n$ using a polynomial). Squaring both sides of the inequality yields $\log^2 n \leq n + \log_2 k$ for all $n > 0$. Dividing each side by $\log 2$ gives $\log^2 n / \log 2 \leq n \log 2 + \log k$ for all $n > 0$. By the fundamental properties of the logarithm, we obtain $\log^2 n / \log 2 \leq \log k2^n$ for all $n > 0$. And since the exponential function is increasing on its argument, also that $\exp \log^2 n / \log 2 \leq \exp \log k2^n$ for all $n > 0$. But $\exp \log k2^n = k2^n$, so that $\exp \log^2 n / \log 2 \leq k2^n$ for all $n > 0$. If we note that $\log^2 n / \log 2$ is just an obfuscated way of writing $\log_2 n \log n$, and $\exp{\log^2 n \log n}$ is just a disguised form of $n^{\log_2 n}$, we obtain $n^{\log_2 n} \leq k2^n$ for all $n > 0$. So for each real $k \geq 1$ and all $n > 0$, the inequality holds (assuming no mistakes).