Prove that $\sqrt{n} \le \sum_{k=1}^n \frac{1}{\sqrt{k}} \le 2 \sqrt{n} - 1$ is true for $n \in \mathbb{N}^{\ge 1}$

Question

I'm trying to solve these induction exercises proposed by the department of mathematics of Oxford University. I don't know how to give a valid proof for the third one which says the following:

Prove that for $n \in \mathbb{N}^{\ge 1}$: $$ \sqrt{n} \le \sum_{k=1}^n \frac{1}{\sqrt{k}} \le 2 \sqrt{n} - 1 $$

My first approach has been to convert the summation into a function in terms of $n$ so that I could find the maximum and minimum values in the interval. However, there doesn't seem to be an easy way to express the summation as a function. Thanks in advance!

Answer 1

Since $$ \sqrt{k+1}-\sqrt{k}=\frac1{\sqrt{k+1}+\sqrt{k}}\tag{1} $$ we have $$ \frac1{2\sqrt{k+1}}\le\sqrt{k+1}-\sqrt{k}\le\frac1{2\sqrt{k}}\tag{2} $$ Summing $(2)$ yields $$ \sum_{k=2}^n\frac1{2\sqrt{k}}\le\sqrt{n}-1\le\sum_{k=1}^{n-1}\frac1{2\sqrt{k}}\tag{3} $$ which implies $$ \sqrt{n}-1+\frac1{2\sqrt{n}}\le\sum_{k=1}^n\frac1{2\sqrt{k}}\le\sqrt{n}-\frac12\tag{4} $$ Therefore, $$ 2\sqrt{n}-2+\frac1{\sqrt{n}}\le\sum_{k=1}^n\frac1{\sqrt{k}}\le2\sqrt{n}-1\tag{5} $$ Combining $(5)$ and $$ \sqrt{n}\le\sqrt{n}+\left(n^{1/4}-n^{-1/4}\right)^2=2\sqrt{n}-2+\frac1{\sqrt{n}}\tag{6} $$ yields $$ \sqrt{n}\le\sum_{k=1}^n\frac1{\sqrt{k}}\le2\sqrt{n}-1\tag{7} $$

Answer 2

In answering a similar question I proved that:

$$\frac{2}{3}N\sqrt{N}\leq\sum_{n=1}^{N}\sqrt{n}\leq\frac{4N+3}{6}\sqrt{N}.$$

This can be achieved through induction, partial summation or a Riemann sums+convexity argument. For this problem, let's try the third way. $f(x)=\frac{1}{\sqrt{x}}$ is a convex function over $[1,N]$, hence the trapezoidal rule overestimates the integral $\int_{1}^{N}\frac{dx}{\sqrt{x}}$: $$\sum_{n=1}^{N}\frac{1}{\sqrt{n}}-\frac{1}{2}\left(\frac{1}{\sqrt{1}}+\frac{1}{\sqrt{N}}\right)\geq 2\sqrt{N}-2,$$ that is just: $$\sum_{n=1}^{N}\frac{1}{\sqrt{n}}\geq 2\sqrt{N}-\frac{3}{2}+\frac{1}{2\sqrt{N}}\tag{1},$$ while the fact that $f(x)$ is decreasing gives: $$\sum_{n=1}^{N}\frac{1}{\sqrt{n}}\leq 1+\int_{1}^{N}\frac{dx}{\sqrt{x}}=2\sqrt{N}-1,\tag{2}$$ establishing the following tight inequality:

$$2\sqrt{N}-\frac{3}{2}\leq \sum_{n=1}^{N}\frac{1}{\sqrt{n}}\leq 2\sqrt{N}-1.$$