# Proving $\sum_{j=1}^n \frac{1}{\sqrt{j}} > \sqrt{n}$ with induction

Problem: Prove with induction that \begin{align*} \sum_{j=1}^n \frac{1}{\sqrt{j}} > \sqrt{n} \end{align*} for every natural number $n \geq 2$.

Attempt at proof: Basic step: For $n = 2$ we have $1 + \frac{1}{\sqrt{2}} > \sqrt{2}$ which is correct.

Induction step: Suppose the assertion holds for some natural number $n$, with $n > 2$. Then we now want to prove that it also holds for $n +1$, i.e. that \begin{align*} \sum_{j=1}^{n+1} \frac{1}{\sqrt{j}} > \sqrt{n+1} \end{align*} Now we have that \begin{align*} \sum_{j=1}^{n+1} \frac{1}{\sqrt{j}} = \sum_{j=1}^n \frac{1}{\sqrt{j}} + \frac{1}{\sqrt{n+1}} > \sqrt{n} + \frac{1}{\sqrt{n+1}} \end{align*} or \begin{align*} \sum_{j=1}^n \frac{1}{\sqrt{j}} + \frac{1}{\sqrt{n+1}} > \frac{\sqrt{n} \sqrt{n+1} + 1}{\sqrt{n+1}} \end{align*}

Now I'm stuck, and I don't know how to get $\sqrt{n+1}$ on the right hand side. Help would be appreciated.

As Daniel Fischer points out in the comments, since you have $$\sum_{j=1}^{n+1} \frac{1}{\sqrt{j}} > \sqrt{n} + \frac{1}{\sqrt{n+1}}$$ it is enough to show $$\sqrt{n} + \frac{1}{\sqrt{n+1}} \geq \sqrt{n+1}$$ or equivalently $\frac{1}{\sqrt{n+1}} \geq \sqrt{n+1} - \sqrt{n}$. A way to show this final inequality is to recall the identity $(a-b)(a+b) = a^2-b^2$ and multiply both sides by $\sqrt{n+1} + \sqrt{n}$, i.e. to use the identity with $a=\sqrt{n+1}$ and $b=\sqrt{n}$: what happens to the LHS? To the RHS?

• I don't understand why it is enough to show that $\sqrt{n} + \frac{1}{\sqrt{n+1}} \geq \sqrt{n+1}$? How did you deduce that? – Kamil Aug 5 '15 at 8:51
• Because you proved half of it already, basically. Look at it this way: you want to show that $A > B$, and you proved so far that $A > C$. So if you manage to show that $C \geq B$, then you get $A > C \geq B$, and therefore in particular $A > B$ as you wanted. – Clement C. Aug 5 '15 at 8:53
• I see. Ok, I did what you said. That gave me $(\sqrt{n+1} + \sqrt{n}) (\frac{1}{\sqrt{n+1}}) \geq ( \sqrt{n+1} - \sqrt{n}) ( \sqrt{n+1} + \sqrt{n})$. But if I distribute on the left side and simplify on the right side, I get $\frac{\sqrt{n+1}}{\sqrt{n+1}} + \frac{\sqrt{n}}{\sqrt{n+1}} > 1$? – Kamil Aug 5 '15 at 9:06
• Which is indeed true as it can be simplified to $1+\frac{\sqrt{n}}{\sqrt{n+1}}>1$, so that the statement is proven (each inequality is equivalent to the previous one, and the last you get is true.) – Clement C. Aug 5 '15 at 9:08

Notice that :

$\sqrt{n}\sqrt{n+1} + 1 > \sqrt{n}\sqrt{n} + 1$

$\sqrt{n}\sqrt{n+1} + 1 > n + 1$

$\sqrt{n}\sqrt{n+1} + 1 > \sqrt{n+1}\sqrt{n+1}$

$\frac{\sqrt{n}\sqrt{n+1} + 1}{\sqrt{n+1}} > \sqrt{n+1}.$