Prove $(\log{n})^2\leq 2^n$ by induction

Question

I've trying to solve this for quite a while now, but not being able to finish the proof.

Prove using induction that $(\log{n})^2\leq 2^n$

Answer 1

For $n=1,2,3$ it's clearly true.

Assume that it holds for $n=k$: $\log k\le 2^{n/2}$.

Then $$ \log(k+1)=\log k\cdot\frac{\log (k+1)}{\log k}=\log k\left(1+\frac{\log(1+\frac{1}{k})}{\log k}\right)\le\log k\left(1+\frac{1}{k\log k}\right)\le 2^{n/2}\cdot 2^{1/2}=2^{(n+1)/2}, $$ as $$ 1+\frac{1}{k\log k}\le \sqrt{2}, \quad \text{for $n\ge 3$} $$

Answer 2

Note that $$ \log(n+1)=\log\left(1+\frac{1}{n}\right)+\log n = \left(1 + \frac{\log(1+1/n)}{\log n}\right)\log n < \sqrt{2}\log n $$ for $n\ge 3$, because $1+\log(4/3)/\log 3\approx 1.262 < \sqrt{2}$, and the numerator $\log(1+1/n)$ is decreasing while the denominator $\log n$ is increasing. So $$ \log^2(n+1)< 2\log^2 n $$ for $n\ge 3$, and hence $\log^2 n \le 2^n$ implies $\log^2(n+1)\le 2^{n+1}$, which is the inductive step you need. You only need to check that the result holds for $n=1,2,3$, which it clearly does.

Answer 3

Try this roadmap:

• $\log n < n$ for all $n$

• $n^2 \le 2^n$ for $n \ne 3$

• handle the case $n=3$ separately.