Proof By Induction: $\sum_{i=1}^n \frac{1}{\sqrt i} > \sqrt n$

Question

Here's what I have so far: $$\sum_{i=1}^n \frac{1}{\sqrt i} > \sqrt n$$ where $n\ge2$.

Test for base case

$$\frac{1}{\sqrt 1} + \frac{1}{\sqrt 2} > \sqrt 2$$

Simplify

$$ 1 + .707... > 1.414... $$ $$ 1.707... > 1.414... $$

This statement is true.

Thus we can assume $\sum_{i=1}^n \frac{1}{\sqrt i} > \sqrt n$ is true for $\forall n$

Now prove $n + 1$

Expand $$\sum_{i=1}^n \frac{1}{\sqrt i} = \frac{1}{\sqrt{1}} + \frac{1}{\sqrt{2}} + ... + \frac{1}{\sqrt{n}} \gt \sqrt n $$

Add the next n in the series, and add it to both sides of the inequality.

$$\frac{1}{\sqrt{1}} + \frac{1}{\sqrt{2}} + ... + \frac{1}{\sqrt{n}} + \frac{1}{\sqrt{n+1}} \gt \sqrt n + \frac{1}{\sqrt{n + 1}} $$

Rewrite $$\frac{1}{\sqrt{1}} + \frac{1}{\sqrt{2}} + ... + \frac{1}{\sqrt{n}} + \frac{1}{\sqrt{n+1}} = \sum_{i=1}^{n + 1} \frac{1}{\sqrt i}$$

LHS is complete now we have to try to make RHS = $\sqrt {n + 1}$

$$\sqrt n + \frac{1}{\sqrt{n + 1}} = \frac{\sqrt{n}\sqrt{n+1} + 1}{\sqrt{n+1}}$$

Given that n > 0

$$\frac{\sqrt{n}\sqrt{n+1} + 1}{\sqrt{n+1}} = \frac{\sqrt{n(n+1)} + 1} {\sqrt{n+1}}$$

Now since this is my first induction involving inequalities or summation, I was hoping you guys could show me what the next step would be, since I'm really not sure. Thanks in advance!

Answer 1

Well. Observe that \begin{align} \sqrt{n}+\frac{1}{\sqrt{n+1}} = \frac{\sqrt{n^2+n}+1}{\sqrt{n+1}}\geq \frac{n+1}{\sqrt{n+1}} =\sqrt{n+1} \end{align}

Answer 2

For the base case, you should prove that $$ 1+\frac{1}{\sqrt{2}}>\sqrt{2} $$ which is equivalent to $\sqrt{2}+1>2$ or $\sqrt{2}>1$; since $2>1$, we are done.

Now assume that the statement is true for $n$; you need to prove that $$ \sum_{i=1}^{n+1}\frac{1}{\sqrt{i}}>\sqrt{n+1} $$ By the induction hypothesis, you know that the left-hand side is greater than $$ \sqrt{n}+\frac{1}{\sqrt{n+1}} $$ so it's sufficient to show that $$ \sqrt{n}+\frac{1}{\sqrt{n+1}}>\sqrt{n+1} $$ which is equivalent to $$ \sqrt{n(n+1)}+1>n+1 $$ Can you finish?

Answer 3

You can prove this without induction. In fact, when $n=1$ it's ok; and when $n>1$, for each $i=1,..,n-1$ we have $$\frac{1}{\sqrt{i}}>\frac{1}{\sqrt{n}}$$

Now, $\sum\limits_{i=1}^n\frac{1}{\sqrt{i}}>n\cdot\frac{1}{\sqrt{n}}=\sqrt{n}$.