# 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?

-
Does it suffice to note that $f(x)=\log x - \sqrt{x}$ satisfies $f'(x)\leq 0$ for $x\geq 4$ and note that the inequality is satisfied for $n=1,2,3,4$? – Chris Taylor Sep 19 '11 at 14:07
What are you "allowed" to use? (Actually, how are you defining $\log$? I assume you mean the natural log there, and a usual definition is as $\log x = \int_1^x \frac{1}{y} \mathrm{d}y$, so some calculus is used.) – Willie Wong Sep 19 '11 at 14:09

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.

-
You need to special case $x=1$ since $f'(x)>0$ for $1<x<\sqrt{2}$. For $x>\sqrt{2}$, $f'(x)<0$, and your argument works for x\ge2. – robjohn Sep 19 '11 at 14:40
@robjohn, thanks. I rushed my answer since others were being published as I was writing. – Grumpy Parsnip Sep 19 '11 at 14:49
I, too, was being sloppy. $1-(1/2)\sqrt{x}\;\begin{array}{c}<\\=\\>\end{array}\;0$ when $x\;\begin{array}{c}>\\=\\<\end{array}\;4$ – robjohn Sep 20 '11 at 0:18
@robjohn: :) Ha. That's too funny. I will correct. – Grumpy Parsnip Sep 20 '11 at 0:42

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

-

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

-
I was typing up that proof right when you posted this. :) – Grumpy Parsnip Sep 19 '11 at 14:10

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

-
$\bigl(e^{\sqrt{n}}\bigr)^2=e^{2\sqrt{n}}$. – Christian Blatter Sep 20 '11 at 10:25
I am substituting $n^2$ for $n$, not squaring each side. Upon thinking about this, we have to consider what happens between $n^2$ and $(n+1)^2$, but that takes a little more work. – marty cohen Sep 23 '11 at 19:42

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

-

I have a ridiculous proof.

Just draw graph and find the lattice or we know $\mathbb{N}\subset\mathbb{R}$.

and $\frac{\mathrm{d}}{\mathrm{dx}}\sqrt{x}=\frac{1}{2\sqrt{x}}>\frac{\mathrm{d}}{\mathrm{dx}}\log x=\frac{1}{x}$ for $x>4$ and for $x=4$, $2>1/4$.

Q.E.D

-
Drawing a graph should almost never be a proof. Derivatives, on the other hand, are fine. – Asaf Karagila Sep 19 '11 at 14:09
It's not a proof in this way, but you can make it a proof by transforming the axes homeomorphically to reach to $\infty$. Then you still need that both functions are continuous and monotonic to proove that the graph didn't "swallow" anything. – leftaroundabout Sep 19 '11 at 14:17
@leftaroundabout: Continuous and monotonic is not enough. Such functions can cross each other. Consider $f(x)=2x$, $g(x)=2x+\sin x$. – Nate Eldredge Sep 19 '11 at 15:05