Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Possible Duplicate:
Proving $\sum\limits_{k=1}^{n}{\frac{1}{\sqrt{k}}\ge\sqrt{n}}$ with induction

How do I prove the following? $$\sqrt{n} < \dfrac{1}{\sqrt{1}} + \dfrac{1}{\sqrt{2}} + \cdots + \dfrac{1}{\sqrt{n}},$$ for all $n \in\mathbb{Z}$, $n\ge 2$.

share|cite|improve this question

marked as duplicate by Srivatsan, t.b., Martin Sleziak, Asaf Karagila, Rudy the Reindeer Jan 4 '12 at 21:54

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

Multiply both sides by $\sqrt{n}$? – user4143 Dec 6 '11 at 20:53
up vote 11 down vote accepted

For any $r \in [1, n]$, we have $$ \frac{1}{\sqrt{r}} \geqslant \frac{1}{\sqrt{n}}. $$ with strict inequality for $1 \leqslant r \lt n$. Adding all these $n$ inequalities, $$ \sum_{r=1}^{n} \frac{1}{\sqrt{r}} \gt n \cdot \frac{1}{\sqrt{n}} = \sqrt{n}. $$

Proof using induction. The OP requested a proof using induction. I am assuming you can handle the base case $n=2$.

Now, assume that the inequality holds for some $n \geqslant 2$; we will verify the inequality for $n+1$: $$ \begin{align*} \sum_{r=1}^{n+1} \frac{1}{\sqrt{r}} &= \sum_{r=1}^{n} \frac{1}{\sqrt{r}} + \frac{1}{\sqrt{n+1}} \\ &\gt \sqrt{n} + \frac{1}{\sqrt{n+1}} \\ &= \sqrt{n+1} + \frac{1}{\sqrt{n+1}} - (\sqrt{n+1} - \sqrt{n}) \\ &= \sqrt{n+1} + \frac{1}{\sqrt{n+1}} - \frac{1}{\sqrt{n+1} + \sqrt{n}} \\ &\gt \sqrt{n+1} , \end{align*} $$ which is what we want to show.

Notice that out second inequality is a bit too crude. robjohn's answer shows how to get a better bound by being more careful.

share|cite|improve this answer
Is there any way to prove it using mathematical induction? – geraldgreen Dec 5 '11 at 23:37
I am not sure why you would want an induction proof. Even if it were possible at all, it will definitely be only more difficult and less enlightening. – Srivatsan Dec 5 '11 at 23:39
Yes, but if one does a routine induction the proof will look harder than the nice simple argument given by Srivatsan. I can do one if you will promise not to accept it. – André Nicolas Dec 5 '11 at 23:44
I have added an induction argument, @John. – Srivatsan Dec 5 '11 at 23:45
@Srivatsan: with induction, you can get a better bound. However, for the bound requested, there is no reason to use induction. – robjohn Dec 5 '11 at 23:50

We can even do better: $$ \sqrt{n}-\sqrt{n-1}=\frac{1}{\sqrt{n}+\sqrt{n-1}}<\frac{1}{2\sqrt{n-1}}\tag{1} $$ Summing, we get $$ \sqrt{n}-1<\frac{1}{2}\left(\frac{1}{\sqrt{1}}+\frac{1}{\sqrt{2}}+\dots+\frac{1}{\sqrt{n-1}}\right)\tag{2} $$ So, for $n\ge2$, $$ \sqrt{n}<1+\frac{1}{2}\left(\frac{1}{\sqrt{1}}+\frac{1}{\sqrt{2}}+\dots+\frac{1}{\sqrt{n-1}}\right)\tag{3} $$ which is a better bound for every $n$.

share|cite|improve this answer

Not the answer you're looking for? Browse other questions tagged or ask your own question.