How to prove $\log n \leq \sqrt n$ over natural numbers?

Question

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?

Answer 1

I would use calculus to show $\sqrt{x} - \log x$ is increasing, together with the observation that $\sqrt{1}-\log 1 > 0$.

Answer 2

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.

Answer 3

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$.

Answer 4

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.$$

Answer 5

Here's a different way to look at this problem. Let $f, g : \mathbb{R} \rightrightarrows \mathbb{R}$ be functions such that

1. $f$ is monotonically increasing.
2. $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

1. $e^x$ is monotonically increasing.
2. $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$.