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?
How to prove $\log n \leq \sqrt n$ over natural numbers?
-
1What 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.) – 2011-09-19
5 Answers
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.
-
0@robjohn: :) Ha. That's too funny. I will correct. – 2011-09-20
I would use calculus to show $\sqrt{x} - \log x$ is increasing, together with the observation that $\sqrt{1}-\log 1 > 0$.
-
0I was typing up that proof right when you posted this. :) – 2011-09-19
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$.
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.$
-
1I 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. – 2011-09-23
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)$.