2

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.

Martin Sleziak
  • 53,687
Kamil
  • 5,139

2 Answers2

2

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?

Clement C.
  • 67,323
  • 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 05 '15 at 08: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 05 '15 at 08: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 05 '15 at 09: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 05 '15 at 09:08
0

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}. $

DiffeoR
  • 834