Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
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.

share|cite|improve this answer
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$.

share|cite|improve this answer

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

share|cite|improve this answer
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.$$

share|cite|improve this answer
$\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)$.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.