Prove by induction that $\sum_{i=1}^n \frac{1}{\sqrt i} > \sqrt n$ for all integers $n \ge 2$

Question

Having trouble with the concept of proving an inequality.

Q: Prove by induction that $\sum_{i=1}^n \frac{1}{\sqrt i} > \sqrt n$ for all integers $n \ge 2$

Here is what I have so far:

Basis ($n=2$)

$\sum_{i=1}^n \frac{1}{\sqrt i} = \frac{1 + \sqrt 2}{\sqrt 2} > \frac{1 + 1}{\sqrt 2} = \sqrt 2$

Inductive Step

(IH): Let $k \ge 2$ be an integer and suppose that $\sum_{i=1}^k \frac{1}{\sqrt i} > \sqrt k$

We want to prove that $\sum_{i=1}^{k+1} \frac{1}{\sqrt i} > \sqrt {k+1}$

So,

$$\sum_{i=1}^{k+1} \frac{1}{\sqrt i} = \left( \sum_{i=1}^k \frac{1}{\sqrt i} \right) + \frac {1}{\sqrt {k+1}}$$

$$\sum_{i=1}^{k+1} \frac{1}{\sqrt i} > \sqrt k + \frac {1}{\sqrt {k+1}}$$

$$\sum_{i=1}^{k+1} \frac{1}{\sqrt i} > \frac{\sqrt{k+1} \sqrt k}{\sqrt{k+1}} + \frac{1}{\sqrt{k+1}}$$

$$\sum_{i=1}^{k+1} \frac{1}{\sqrt i} > \frac{\sqrt{k+1} \sqrt k + 1}{\sqrt{k+1}}$$

And now I do not understand where to go from here to get my proof. I don't know what I'm supposed to compare here?

Answer 1

Based on your derivation, it suffices to show that $$ \sqrt{k+1}\sqrt{k} + 1 \ge k+1. $$ This can be shown as follow: $$ (k+1)k = k^2 + k > k^2. $$ Then you're done!

Answer 2

Hint: You can show that $\sqrt{k+1}<\sqrt{k}+\frac{1}{\sqrt{k+1}}$.

Answer 3

Induction is not at all necessary here: if $1\le i\le n$, so $1\le \sqrt i \le \sqrt n$, whence $\dfrac 1{\sqrt n}\le \dfrac 1{\sqrt i}\le 1$, and $$ \sum_{i=1}^n \frac{1}{\sqrt n}=\frac n{\sqrt n}=\sqrt n\le \sum_{i=1}^n \frac{1}{\sqrt i} \le \sum_{i=1}^n 1=n. $$ Furthermore, if $n\ge 2$, all but one of the inequalities $\frac1{\sqrt i}<1$ and all but one of $\frac1{\sqrt n}<\frac1{\sqrt i}$ are strict, so really $$\sqrt n < \sum_{i=1}^n \frac{1}{\sqrt i} <n. $$

Answer 4

To make the proof work, you need to show that $\sqrt{n}+\dfrac1{\sqrt{n+1}} \gt \sqrt{n+1} $.

This is the same as

$\begin{array}\\ \dfrac1{\sqrt{n+1}} &\gt \sqrt{n+1}-\sqrt{n}\\ &=(\sqrt{n+1}-\sqrt{n})\dfrac{\sqrt{n+1}+\sqrt{n}}{\sqrt{n+1}+\sqrt{n}}\\ &=\dfrac{1}{\sqrt{n+1}+\sqrt{n}}\\ \end{array} $

which is obvious.

You can get a more precise result by noting that $\dfrac1{\sqrt{n+1}} =\dfrac{1}{\sqrt{n+1}+\sqrt{n}} $ implies that

$\dfrac{1}{2\sqrt{n+1}} \lt \sqrt{n+1}-\sqrt{n} \lt \dfrac{1}{2\sqrt{n}} $.

Summing the left side,

$\sum_{n=1}^m \dfrac{1}{2\sqrt{n+1}} \lt \sum_{n=1}^m (\sqrt{n+1}-\sqrt{n}) =\sqrt{m+1}-1 \lt \sqrt{m+1} $ so that $\sum_{n=2}^{m+1} \dfrac{1}{2\sqrt{n}} \lt \sqrt{m+1} $ or $\sum_{n=2}^{m} \dfrac{1}{\sqrt{n}} \lt 2\sqrt{m} $ so $\sum_{n=1}^{m} \dfrac{1}{\sqrt{n}} \lt 2\sqrt{m}+1 $.

Summing the right side,

$\sum_{n=1}^{m-1} \dfrac{1}{2\sqrt{n}} \gt \sum_{n=1}^{m-1} (\sqrt{n+1}-\sqrt{n}) =\sqrt{m}-1 $ so that $\sum_{n=1}^{m-1} \dfrac{1}{\sqrt{n}} \gt 2\sqrt{m}-2 $ so $\sum_{n=1}^{m} \dfrac{1}{\sqrt{n}} \gt 2\sqrt{m}-1+\frac1{\sqrt{m}} \gt 2\sqrt{m}-1 $.

Therefore $\sum_{n=1}^{m} \dfrac{1}{\sqrt{n}}$ is between $2\sqrt{m}-1 $ and $2\sqrt{m}+1 $.