Mathematical Induction for $n \geq 1$

Question

I want to prove, using mathematical induction, the following proposition:

$$1+\frac{1}{\sqrt{2}}+...+\frac{1}{\sqrt{n}}\:\ge \sqrt{n}, \forall n \geq 1 \in \mathbb{N}$$

My thesis is:

$$\frac{1}{\sqrt{n}}+\frac{1}{\sqrt{n+1}}\ge \sqrt{n+1}, \forall n \geq 1 \in \mathbb{N}$$

I've proved the inequality for $n=1$, but after that I'm not being able to do the rest :/

Thank you for the help!

false............. The sum is larger than $\sqrt n,$ it is approximately $2 \sqrt n$ minus a modest constant — Will Jagy, Sep 30 '17 at 18:03
What do you think you should do? I don't see any of your writing or thinking, so I don't know what you're stuck on. Have you even tried to show the base case ($n=2$)? — Eric Towers, Sep 30 '17 at 18:10
@EricTowers Yes, i've done that, and i'm stuck after that, I've study mathematical induction but i'm not understand how can i apply that for this example — Miguel Ferreira, Sep 30 '17 at 18:12
@gammatester Yes, that's what i'm being asked for :P But you can also show that approach :) — Miguel Ferreira, Sep 30 '17 at 18:24
What has to be proved in the inductive step? What can you use and where are you stuck? — gammatester, Sep 30 '17 at 18:45
Ok this is a start. Completely write down the inequality for $n+1$ and review your thesis. — gammatester, Sep 30 '17 at 18:49
No the correct 'thesis' would be $${\sqrt{n}}+\frac{1}{\sqrt{n+1}}\ge \sqrt{n+1}$$ or $${\sqrt{n}}+\frac{1}{\sqrt{n+1}}- \sqrt{n+1} \ge 0$$ write this as single fraction and continue. — gammatester, Sep 30 '17 at 19:16
@gammatester Ok, i've now write it as a single fraction, i got: $$\frac{\sqrt{n}\left(\sqrt{n+1}\right)+1}{\sqrt{n+1}}$$ but i still can't get this to look equal to $$\sqrt{n+1}$$ — Miguel Ferreira, Sep 30 '17 at 19:21
You forgot the third term, you should get $$\frac{\sqrt{n}\sqrt{n+1}+1-(n+1)}{\sqrt{n+1}}$$ Can you show that the numerator is $\ge 0?$ — gammatester, Sep 30 '17 at 19:26
@gammatester Ok, done. I've reached that expression. I know that for the smaller n (1), the numerator will be bigger than zero — Miguel Ferreira, Sep 30 '17 at 19:30
Why only for 'smaller' $n?$ $\sqrt{n}\sqrt{n+1}$ is always $\ge n!$ — gammatester, Sep 30 '17 at 19:33
It shows that $$\sqrt{n}+\frac{1}{\sqrt{n+1}} \ge \sqrt{n+1}$$ and this was the result needed to finish the incduction step. — gammatester, Sep 30 '17 at 19:37
Oh, i'm no understanding! Thank you very much for the amazing help!! :) — Miguel Ferreira, Sep 30 '17 at 19:40

score 1 · Answer 1 · answered Sep 30 '17 at 19:01

For base cases $n=1$ we get that $1 \geq \sqrt{1}$

For $n=2$ we get that $1+\frac{1}{\sqrt{2}} \geq \sqrt{2}$.

Assume that $1+\frac{1}{\sqrt{2}} +\cdots +\frac{1}{\sqrt{n}} \geq \sqrt{n}$.

And we want to prove that $1+\frac{1}{\sqrt{2}} +\cdots +\frac{1}{\sqrt{n}}+\frac{1}{\sqrt{n+1}} \geq \sqrt{n+1}$

From the assumption step we know that $1+\frac{1}{\sqrt{2}} +\cdots +\frac{1}{\sqrt{n}} \geq \sqrt{n}$

Substitute instead of $1+\frac{1}{\sqrt{2}} +\cdots +\frac{1}{\sqrt{n}}$ the $\sqrt{n}$.

To get $\sqrt{n}+\frac{1}{\sqrt{n+1}} \geq \sqrt{n+1}$ (This what you need to prove).

thank you very much for the help! And how can I prove that last line? I've done the sum but it's giving me something really different that what we need to prove :O — Miguel Ferreira, Sep 30 '17 at 19:14

score 1 · Answer 2 · answered Sep 30 '17 at 19:37

The Inductive Step

Since $$ \begin{align} \sqrt{n}-\sqrt{n-1} &=\frac1{\sqrt{n}+\sqrt{n-1}}\\ &\le\frac1{\sqrt{n}}\tag1 \end{align} $$ we have $$ \begin{align} \sum\limits_{k=1}^n\frac1{\sqrt{k}} &=\color{#C00}{\sum\limits_{k=1}^{n-1}\frac1{\sqrt{k}}}+\frac1{\sqrt{n}}\tag2\\ &\ge\color{#C00}{\sqrt{n-1}}+\frac1{\sqrt{n}}\tag3\\[9pt] &\ge\sqrt{n}\tag4 \end{align} $$ Explanation:
$(2)$: expand sum
$(3)$: inductive hypothesis
$(4)$: apply $(1)$

score 0 · Answer 3 · answered Sep 30 '17 at 19:25

$$\sqrt n\;+\frac {1}{\sqrt {n+1}}\geq \sqrt {n+1}\iff \frac {1}{\sqrt {n+1}}\;\geq \sqrt {n+1}-\sqrt n=$$ $$=(\sqrt {n+1}-\sqrt n)\cdot \frac {\sqrt {n+1}+\sqrt n}{\sqrt {n+1}+\sqrt n}=\frac {1}{\sqrt {n+1}+\sqrt n}\iff$$ $$\iff \frac {1}{\sqrt {n+1}}\geq \frac {1}{\sqrt {n+1}+\sqrt n}\;.$$

score 0 · Answer 4 · 2017-09-30T20:37:10.007

For $n \ge1 $, we have $$n \ge n-1 + \frac1{n+1}$$ $$\iff n \ge n+1-2 + \frac1{n+1}$$ $$\Rightarrow n \ge (\sqrt{n+1} - \frac1{\sqrt{n+1}})^2$$ $$\Rightarrow \sqrt{n} \ge \sqrt{n+1} - \frac1{\sqrt{n+1}}$$

Now $\sqrt{1} \ge 1$. Assume $\sum_{r=1}^n \frac1{\sqrt{r}} \ge \sqrt{n}$.

Then $$\sum_{r=1}^n \frac1{\sqrt{r}} \ge \sqrt{n} \ge \sqrt{n+1} - \frac1{\sqrt{n+1}}$$

$$\Rightarrow \sum_{r=1}^{n+1} \frac1{\sqrt{r}} \ge \sqrt{n+1}$$

Hence , by induction , $\forall n \in \mathbb{N}, \sum_{r=0}^n \frac1{\sqrt{r}} \ge \sqrt{n}$.

Mathematical Induction for $n \geq 1$

4 Answers4