2

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!

Alex
  • 443
  • Not exactly relevant to your question, but just thought I'd point out ...we can assume [P(n)] is true ∀n is incorrect as that assumes what you are trying to prove is true. You want to assume the statement holds $\forall n < k$ and then prove $k+1$ holds. – DividedByZero Apr 01 '18 at 23:38
  • Also: https://math.stackexchange.com/q/1385126/42969, https://math.stackexchange.com/q/2076108/42969. – Martin R Apr 02 '18 at 08:22

3 Answers3

5

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}

Jacky Chong
  • 25,739
  • Oh right! Since $\sqrt{n^2 + n} \gt n$ given that $n > 2$. Squaring both sides makes this even more obvious $n^2 + n > n^2$

    Which then you can use to say $\sum_{i=1}^{n + 1} \gt \frac {\sqrt{n^2+n} + 1}{\sqrt{n+1}} \gt \sqrt{n+1}$ which implies the summation has to be greater than $\sqrt {n + 1}$ thus it is proven by induction!

     – Alex Apr 01 '18 at 22:39
  • @Alex Yes. You got it. – Jacky Chong Apr 01 '18 at 23:03
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}$.

Martín Vacas Vignolo
  • 4,710
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?

egreg
  • 238,574