-3

I am just starting out learning mathematical induction and I got this homework question to prove with induction but I am not managing. $$\sum_{k=1}^n\frac1{\sqrt k}<2\sqrt n$$ Please help!

mari
  • 13

2 Answers2

5

One may observe that, for $n>1$, $$ \begin{align} \sum_{k=1}^n \frac{1}{2\sqrt{k}}&= \sum_{k=1}^n \frac{1}{\sqrt{k} + \sqrt{k}} \\&\color{red}{<} \sum_{k=1}^n \frac{1}{\sqrt{k} + \sqrt{k-1}} \\&=\sum_{k=1}^n \frac{\sqrt{k} - \sqrt{k-1}}{(\sqrt{k} + \sqrt{k-1})(\sqrt{k} - \sqrt{k-1})} \\&= \sum_{k=1}^n (\sqrt{k} - \sqrt{k-1}) \\& = \sqrt{n} \end{align} $$ giving that

$$ \sum_{k=1}^n \frac{1}{\sqrt{k}}<2 \sqrt{n}, \quad n=1,2,3,\cdots. $$

Olivier Oloa
  • 120,989
  • Quote: "prove with induction". (And yes, the other argument is neat.) – Did Oct 11 '16 at 09:36
  • @mari Apparently the OP question has been modified. I think I'm going to leave the related answer above. – Olivier Oloa Oct 11 '16 at 09:40
  • 2
    Simplifying a telescoping sum uses induction anyway. – Bernard Oct 11 '16 at 10:44
  • @Bernard Not really, or rather, in a very weak sense: $$\sum_{k=1}^na_k-a_{k-1}=\sum_{k=1}^na_k-\sum_{k=1}^na_{k-1}=\sum_{k=1}^na_k-\sum_{k=0}^{n-1}a_k=\left(\sum_{k=1}^{n-1}a_k+a_n\right)-\left(a_0+\sum_{k=1}^{n-1}a_k\right)$$ hence, $$\sum_{k=1}^na_k-a_{k-1}=a_n-a_0$$ – Did Oct 11 '16 at 14:59
  • @Did: From a pragmatic point of view, I agree with you. The set theory point of view, even the first equality has induction hidden behind. – Bernard Oct 11 '16 at 15:04
  • @Bernard Yes I know (see "in a very weak sense") -- but from this point of view the remark becomes so general that it somewhat loses its edge. – Did Oct 11 '16 at 15:45
2

Induction step

Suppose for some $n\ge1$, one has $\;\displaystyle\sum_{i=1}^n\frac1{\sqrt k}<2\sqrt n$. Then $$\sum_{i=1}^{n+1}\frac1{\sqrt k}=\sum_{i=1}^{n}\frac1{\sqrt k}+\frac1{\sqrt{n+1}}<2\sqrt n+\frac1{\sqrt{n+1}}. $$ Now \begin{align} 2\sqrt n+\frac1{\sqrt{n+1}}<2\sqrt{n+1}&\iff\frac1{2\sqrt{n+1}} <\sqrt{n+1}-\sqrt n=\frac 1{\sqrt{n+1}+\sqrt n}\\ &\iff 2\sqrt{n+1}>\sqrt{n+1}+\sqrt n\iff\sqrt{n+1}>\sqrt n. \end{align}

Without induction:

$\displaystyle\sum_{i=1}^n\frac1{\sqrt k}$ is a lower Riemann sum for the (improper) Riemann integral $$\displaystyle\int_0^n\frac{\mathrm d\mkern1mu x}{\sqrt x}=2\sqrt x\,\biggr\rvert_0^n=2\sqrt n.$$

Bernard
  • 175,478