<s>[INST] Induction: show that $\sum\limits_{k=1}^n \frac{1}{\sqrt{k}} < 2 \sqrt{n}$ for all n $\in Z_+$ The question:
show by using induction that $\sum\limits_{k=1}^n \frac{1}{\sqrt{k}} < 2 \sqrt{n}$ for all n $\in Z_+$
My attempt at a solution:
The base case $n = 1$ is true.
First we use the inductive assumption that the statement holds for some $k = n$
This gives us:
$\frac{1}{\sqrt{1}} + ... + \frac{1}{\sqrt{n}} < 2 \sqrt{n}$
Then we have to prove that it holds true for $k = n+1$
$\frac{1}{\sqrt{1}} + ... + \frac{1}{\sqrt{n+1}} < 2 \sqrt{n+1}$
This means that:
$2 \sqrt{n+1} - 2 \sqrt{n} > \frac{1}{\sqrt{n+1}}$
We can start by factoring out $2$:
$2 (\sqrt{n+1} -  \sqrt{n}) > \frac{1}{\sqrt{n+1}}$
We can then multiply with ${\sqrt{n+1}}$:
$2 ((n+1) -  \sqrt{n}\sqrt{n+1}) > 1$
But I am stuck here... Please help me out with the last steps!
Thank you very much!
 [/INST] Note that, by induction hypothesis
$$
\sum_{k=1}^{n+1} \frac{1}{\sqrt{k}} < 2\sqrt{n} + \frac{1}{\sqrt{n+1}}
$$
The RHS is $<2\sqrt{n+1}$ iff
$$
\frac{1}{\sqrt{n+1}} < 2(\sqrt{n+1} - \sqrt{n})
$$
$$
\Leftrightarrow \frac{\sqrt{n+1} + \sqrt{n}}{\sqrt{n+1}} < 2(n+1-n) = 2
$$
$$
\Leftrightarrow 1 + \sqrt{\frac{n}{n+1}} < 2
$$
$$
\Leftrightarrow \sqrt{n} < \sqrt{n+1}
$$
which is true.
</s>