2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ @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. $\endgroup$ – John Doe Nov 11 '17 at 19:45
  • 1
    $\begingroup$ Hint: Show $\log(n+1)-\log(n)<\frac{1}{n}$ and $\sqrt{n+1}-\sqrt{n}>\frac{1}{n}$ for $n$ large enough enough. $\endgroup$ – Thomas Andrews Nov 11 '17 at 19:46
  • $\begingroup$ Don't put primary content into comments, add the information to the question. @JohnDoe $\endgroup$ – Thomas Andrews Nov 11 '17 at 19:47
  • $\begingroup$ Possible duplicate of Prove that $\sqrt{n} > \ln n$ $\endgroup$ – Dietrich Burde Nov 11 '17 at 19:55
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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