2
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Kamil Aug 5 '15 at 8:51
  • $\begingroup$ 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. $\endgroup$ – Clement C. Aug 5 '15 at 8:53
  • $\begingroup$ 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$? $\endgroup$ – Kamil Aug 5 '15 at 9:06
  • $\begingroup$ 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.) $\endgroup$ – Clement C. Aug 5 '15 at 9:08
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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