How to prove $\log n \leq \sqrt n$ over natural numbers? It seems like $$\log n \leq \sqrt n \quad \forall n \in \mathbb{N} .$$ I've tried to prove this by induction where I use $$ \log p + \log q \leq \sqrt p \sqrt q $$ when $n=pq$, but this fails for prime numbers. Does anyone know a proof?
 A: 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.
A: I would use calculus to show $\sqrt{x} - \log x$ is increasing, together with the observation that $\sqrt{1}-\log 1 > 0$.
A: Here is a proof of a somewhat weaker inequality that does not use calculus:
Put $m:=\lceil\sqrt{n}\>\rceil$. The set $\{2^0,2^1,\ldots,2^{m-1}\}$ is a subset of the set $\{1,2,\ldots,2^{m-1}\}$; therefore we have the inequality $m\leq 2^{m-1}$ for all $m\geq1$. It follows that
$$\log n=2\log\sqrt{n}\leq 2\log m\leq 2(m-1)\log2\leq 2\log2\>\sqrt{n}\ ,$$
where $2\log2\doteq1.386$.
A: That's the same as $n \le e^{\sqrt n}$ or $n^2 \le e^n$.
If we allow the power series for $e^x$, 
$e^n > n^3/6$ so $e^n > n^2$ for $n \ge 6$.
If we don't allow the power series, we can instead prove by induction that
$n^2 < 2^n$ (which, of course, is better) for $n \ge 5$:
True for $n = 5$; if true for $n \ge 5$,
$$\frac{(n+1)^2}{2^{n+1}} = \frac{n^2}{2^n}\frac{(1+1/n)^2}{2} \le (6/5)^2/2 = 36/50 < 1.$$
A: Bigger by a Factor
Using $e^x\ge1+x$, and substituting $e^x=\sqrt{u}$ and $e^2u=n$, we get
$$
\begin{align}
e^x\ge1+x
&\implies\sqrt{u}\ge1+\frac12\log(u)=\frac12\log(e^2u)\\
&\implies\frac2e\sqrt{n}\ge\log(n)
\end{align}
$$
which is stronger than $\sqrt{n}\ge\log(n)$.

Bigger by an Offset
we could also set $4u=n$, which gives
$$
\sqrt{u}\ge1+\frac12\log(u)
\implies\sqrt{n}\ge2(1-\log(2))+\log(n)
$$
which is also stronger than $\sqrt{n}\ge\log(n)$.
A: Here's a different way to look at this problem. Let $f, g : \mathbb{R} \rightrightarrows \mathbb{R}$ be functions such that

*

*$f$ is monotonically increasing.

*$f(x) > g(x)$ for all $x$.

I claim that this implies $f^{-1}(x) < g^{-1}(x)$ for all $x$.
Proof: Suppose toward a contradiction that there is some $x \in \mathbb{R}$ such that $f^{-1}(x) \geq g^{-1}(x)$. By (1), we have
$$
\tag{*}
x = f(f^{-1}(x)) \geq f(g^{-1}(x)).
$$
And by (2), we have
$$
\tag{**}
f(g^{-1}(x)) > g(g^{-1}(x)) = x.
$$
Combining (*) and (**), we get that $x > x$, which is a contradiction.

Applying this fact to $e^x$ and $x^2$, we can show that

*

*$e^x$ is monotonically increasing.

*$e^x > x^2$ for all $x$.

This would imply that $\ln x < \sqrt x$ for all $x$. These statements should be simpler to prove. At the very least, it's more intuitive (in my opinion) than working with $\ln x$ and $\sqrt x$.
