# Non-induction proof of $2\sqrt{n+1}-2<\sum_{k=1}^{n}{\frac{1}{\sqrt{k}}}<2\sqrt{n}-1$

Prove that $$2\sqrt{n+1}-2<\sum_{k=1}^{n}{\frac{1}{\sqrt{k}}}<2\sqrt{n}-1.$$

After playing around with the sum, I couldn't get anywhere so I proved inequalities by induction. I'm however interested in solutions that don't use induction, if there are some (relatively simple ones, since I'm high-school student).

Also any advice for determining if a sum can be written in "compact" form? For example, $\displaystyle \sum_{k=1}^{n}{(-1)^{k-1}k}$ is actually $\displaystyle-\frac{n}{2}$ for even $n$ and $\displaystyle\frac{n+1}{2}$ for odd $n$.

-
I would try the series-integral comparison, which is legal because the integrand is nonincresing positive. –  1015 Feb 18 '13 at 11:20

I’d just about bet that the inequality was derived from the observation that

$$\int_1^{n+1}\frac1{\sqrt x}dx<\sum_{k=1}^n\frac1{\sqrt k}<1+\int_1^n\frac1{\sqrt x}dx\;,$$

which can be made from a graph of $y=\frac1{\sqrt x}$ showing rectangles for the appropriate upper and lower Riemann sums.

Since $$\int x^{-1/2}dx=2x^{1/2}+C\;,$$

this immediately yields

$$2\sqrt{n+1}-2<\sum_{k=1}^n\frac1{\sqrt k}<2\sqrt n-1\;.$$

It’s a non-inductive proof, and it’s accessible to those high-school students who have had a decent calculus course.

-

Mean Value Theorem can also be used,

Let $\displaystyle f(x)=\sqrt{x}$

$\displaystyle f'(x)=\frac{1}{2}\frac{1}{\sqrt{x}}$

Using mean value theorem we have:

$\displaystyle \frac{f(n+1)-f(n)}{(n+1)-n}=f'(c)$ for some $c\in(n,n+1)$

$\displaystyle \Rightarrow \frac{\sqrt{n+1}-\sqrt{n}}{1}=\frac{1}{2}\frac{1}{\sqrt{c}}$....(1)

$\displaystyle \frac{1}{\sqrt{n+1}}<\frac{1}{\sqrt{c}}<\frac{1}{\sqrt{n}}$

Using the above ineq. in $(1)$ we have,

$\displaystyle \frac{1}{2\sqrt{n+1}}<\sqrt{n+1}-\sqrt{n}<\frac{1}{2\sqrt{n}}$

Adding the left part of the inequality we have,$\displaystyle\sum_{k=2}^{n}\frac{1}{2\sqrt{k}}<\sum_{k=2}^{n}(\sqrt{k}-\sqrt{k-1})=\sqrt{n}-1$

$\Rightarrow \displaystyle\sum_{k=2}^{n}\frac{1}{\sqrt{k}}<2\sum_{k=2}^{n}(\sqrt{k}-\sqrt{k-1})=2(\sqrt{n}-1)$

$\Rightarrow \displaystyle1+\sum_{k=2}^{n}\frac{1}{\sqrt{k}}<1+2\sum_{k=2}^{n}(\sqrt{k}-\sqrt{k-1})=2\sqrt{n}-2+1=2\sqrt{n}-1$

$\Rightarrow \displaystyle\sum_{k=1}^{n}\frac{1}{\sqrt{k}}<2\sqrt{n}-1$

Similarly adding the right side of the inequality we have,

$\displaystyle\sum_{k=1}^{n}\frac{1}{2\sqrt{k}}>\sum_{k=1}^{n}(\sqrt{k+1}-\sqrt{k})=\sqrt{n+1}-1$

$\Rightarrow \displaystyle\sum_{k=1}^{n}\frac{1}{\sqrt{k}}>2(\sqrt{n+1}-1)$

This completes the proof.

$\displaystyle 2\sqrt{n+1}-2<\sum_{k=1}^{n}{\frac{1}{\sqrt{k}}}<2\sqrt{n}-1.$

-