Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|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
1  
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

5 Answers 5

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|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|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|improve this answer
    
I was typing up that proof right when you posted this. :) –  Grumpy Parsnip Sep 19 '11 at 14:10

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

enter image description here

Q.E.D

share|improve this answer
8  
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
2  
@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

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

Your Answer

 
discard

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.