# Prove that $\ln n < \sqrt n$ for all natural numbers n by induction

Could you help me to prove that $\ln n < \sqrt n$ for all natural numbers by induction?

I chose the basic step for n=1, that’s true, then I suggested that it’s true for n, so $\ln n <n \sqrt n$ and I don’t know how to prove that $\ln (n+1) < \sqrt {n+1}$. I can use the fact that $\sqrt {(\ln n)^2+1}< \sqrt {n+1}$. If I find a way to prove that $\ln (n+1) < \sqrt {(\ln n)^2+1}$, I’m done

• @Dr. Sonnhard Graubner The basic step is for n=1, that’s true, then I suggest that it’s true for n, so $\ln n < \sqrt n$ and I don’t know how to prove that $\ln (n+1) < \sqrt {n+1}$. I can use the fact that $\sqrt {(\ln n)^2 + 1} < \sqrt {n+1}$. If I find a way to prove that $\ln (n+1) < \sqrt{(\ln n)^2+1}$, I’m done. – John Doe Nov 11 '17 at 19:45
• Hint: Show $\log(n+1)-\log(n)<\frac{1}{n}$ and $\sqrt{n+1}-\sqrt{n}>\frac{1}{n}$ for $n$ large enough enough. – Thomas Andrews Nov 11 '17 at 19:46
• Don't put primary content into comments, add the information to the question. @JohnDoe – Thomas Andrews Nov 11 '17 at 19:47
• Possible duplicate of Prove that $\sqrt{n} > \ln n$ – Dietrich Burde Nov 11 '17 at 19:55

## 1 Answer

If you know the result $1+x<e^x$ for $x>0$ then you know that $\log(1+x)<x$ for $x>0$.

First verify for $n=1,2,3,4,5$.

Now, for $n\geq 5$, you have:

\begin{align}\log(n+1)&=\log(n)+\left(\log(n+1)-\log(n)\right)\\ &=\log(n)+\log\left(1+\frac{1}{n}\right)\\ &<\log(n)+\frac{1}{n} \end{align}

We also have:

\begin{align} \sqrt{n+1}&=\sqrt{n}+\left(\sqrt{n+1}-\sqrt{n}\right)\\ &=\sqrt{n}+\frac{1}{\sqrt{n}+\sqrt{n+1}}\\ &\geq \sqrt n+\frac{1}{2\sqrt{n+1}} \end{align}

We can show that $2\sqrt{n+1}\leq n$ for $n>2+\sqrt{8}$ or $n\geq 5$. Thus: $$\sqrt{n+1}\geq\sqrt{n}+\frac{1}{n}$$

This means that if $\log(n)<\sqrt{n}$ and $n\geq 5$ then:

$$\log(n+1)<\log(n)+\frac{1}{n}<\sqrt{n}+\frac{1}{n}<\sqrt{n+1}$$

You can use the approach that Mark Viola wrote to lessen the problem. If:

$$\frac{2}{\sqrt{n}}+\frac{1}{n^2}<1\tag{1}$$ then $$\left(\sqrt{n}+\frac{1}{n}\right)^2<n+1.$$

But $\frac{2}{\sqrt{n}}+\frac{1}{n^2}$ is decreasing and the inequality (1) is true for $n=5$ so it is true for $n\geq 5$.