How to prove $\log n \leq \sqrt n$ over natural numbers?
Solution 1:
Consider the function $f(x)=\log x-\sqrt{x}$. Then $f'(x)=(1-(1/2)\sqrt{x})/x$, and you can easily see this is negative when $x\geq 4$. So this means that if $f(1),f(2),f(3)<0$ and $f(4)<0$, then so is $f(n)$ for all $n>4$. But it's easy to verify that $f(1),f(2),f(3),f(4)<0$, so you're done.
Solution 2:
I would use calculus to show $\sqrt{x} - \log x$ is increasing, together with the observation that $\sqrt{1}-\log 1 > 0$.