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

Question

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

Answer 1

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