Induction: show that $\sum\limits_{k=1}^n \frac{1}{\sqrt{k}} < 2 \sqrt{n}$ for all n $\in Z_+$

Question

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!

Answer 1

The function $x\mapsto 1/\sqrt x$ is decreasing on $]0,+\infty[$, so for $k\geq1$ $$\frac{1}{\sqrt{k}}\leq\int_{k-1}^{k}\frac{\mathrm dx}{\sqrt x}.$$ Summing up from $k=1$ to $n$ we get $$\sum_{k=1}^n\frac1{\sqrt k}\leq \int_0^n\frac{\mathrm dx}{\sqrt x}=2\sqrt{n}.$$

Answer 2

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.