0
$\begingroup$

So, I know that for my base case I use $n=1$, and that for the inductive hypothesis we assume the pattern holds until the $n-th$ iteration. Then use that to prove the $(n+1)-th$ iteration ($\Bbb P(n)\implies\Bbb P(n+1)$). The part that is giving me the most trouble is how to actually use the inductive hypothesis given that you're dealing with two inequalities. The algebra of having so many square-roots is also giving me a hard time if you know any hints. Thanks.

$\endgroup$
  • $\begingroup$ That upper bound is absurdly large. Should the numerator be $1$ instead of $n$? $\endgroup$ – marty cohen May 22 at 4:08
2
$\begingroup$

If you know $\sqrt{n} \le \sum_{k=1}^n \frac{1}{\sqrt{k}}$ then adding $\frac{1}{\sqrt{n+1}}$ to both sides yields $$\sqrt{n} + \frac{1}{\sqrt{n+1}} \le \sum_{k=1}^{n+1} \frac{1}{\sqrt{k}}.$$ It then suffices to show $$\sqrt{n+1} \le \sqrt{n} + \frac{1}{\sqrt{n+1}},$$ which I leave to you.


If you know $\sum_{k=1}^n \frac{1}{\sqrt{k}} < \sqrt{n} + \frac{n}{\sqrt{n+1}}$ then adding $\frac{1}{\sqrt{n+1}}$ to both sides yields $$\sum_{k=1}^{n+1} \frac{1}{\sqrt{k}} < \sqrt{n} + \frac{n + 1}{\sqrt{n+1}} = \sqrt{n} + \sqrt{n+1}.$$ It then suffices to show $$\sqrt{n} \le \frac{n+1}{\sqrt{n+2}},$$ which I leave to you.

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