4

Prove using Mathematical Induction that for all natural numbers ($n>0$):

$$ \frac 1 {\sqrt{1}} + \frac 1 {\sqrt{2}} + \cdots + \frac 1 {\sqrt{n}} \ge \sqrt{n}. $$ 

 Proof by Induction:
         Let P(n) denote    1/ √1 + 1/ √2 +  … + 1/ √n ≥  √n
 Base Case: n = 1, P(1) = 1/√1 ≥ √1
  The base cases holds true for this case since the inequality for P(1) holds true.

  Inductive Hypothesis: For every n = k > 0 for some integer k 
  P(k) = 1/ √1 + 1/ √2 +  … + 1/ √k ≥  √k, p(k) holds true for any integer k

 Inductive Step:
          P(k + 1)) = 1/ √1 + 1/ √2 +  … + 1/ √k  + 1/ √(k + 1) ≥  √k + √(k+1)
         √k + √(k+1) > √(k+1)   (this is where I got stuck)
Michael Hardy
  • 1
geforce
  • 217

4 Answers4

3

Assuming $\sum_{i=1}^n \frac{1}{\sqrt{i}} \geq \sqrt{n}$, we have \begin{align*} \sum_{i=1}^{n+1} \frac{1}{\sqrt{i}} &= \sum_{i=1}^n \frac{1}{\sqrt{i}} + \frac{1}{\sqrt{n+1}} \\ &\geq \sqrt{n} + \frac{1}{\sqrt{n+1}} \\ &= \frac{\sqrt{n^2+n} + 1}{\sqrt{n+1}} \\ &\geq \frac{\sqrt{n^2} + 1}{\sqrt{n+1}} = \frac{n+1}{\sqrt{n+1}} = \sqrt{n+1}. \end{align*}

symmetricuser
  • 3,779
2

Hint: Use $\frac{1}{\sqrt{k+1}}\geq\sqrt{k+1}-\sqrt{k}$ on inductive step.

alans
  • 6,475
2

say it is true for $n=k$ in other words $$1/\sqrt{1}+1/\sqrt{2}+\cdots+1/\sqrt{k}\geq\sqrt{k}$$ then for $n=k+1$ $$1/\sqrt{1}+1/\sqrt{2}+\cdots+1/\sqrt{k}+1/\sqrt{k+1}\geq \sqrt{k}+1/\sqrt{k+1}=(\sqrt{k^2+k}+1)/\sqrt{k+1}\geq(\sqrt{k^2}+1)/\sqrt{k+1}=(k+1)/\sqrt{k+1}=\sqrt{k+1}$$

Michael Hardy
  • 1
Arian
  • 6,277
2

You know that

$$\frac{1}{\sqrt{1}}+\frac{1}{\sqrt{2}}+\cdots+\frac{1}{\sqrt{k}} \geq \sqrt{k}$$$$

and want to prove that:

$$\frac{1}{\sqrt{1}}+\frac{1}{\sqrt{2}}+\cdots+\frac{1}{\sqrt{k+1}} \geq \sqrt{k+1}$$$$

Add $\sqrt{k+1}-\sqrt{k}$ to both sides of first inequality, you get:

$$\frac{1}{\sqrt{1}}+\frac{1}{\sqrt{2}}+\cdots+\frac{1}{\sqrt{k}} +\sqrt{k+1}-\sqrt{k}\geq \sqrt{k+1}$$

But:

$$\sqrt{k+1}-\sqrt{k}=\frac{(\sqrt{k+1}+\sqrt{k})(\sqrt{k+1}-\sqrt{k})}{(\sqrt{k+1}+\sqrt{k})}=\frac{k+1-k}{(\sqrt{k+1}+\sqrt{k})}=\frac{1}{(\sqrt{k+1}+\sqrt{k})}\leq \\ \leq \frac{1}{\sqrt{k+1}}$$

So:

$$\sqrt{k+1} \leq \frac{1}{\sqrt{1}}+\frac{1}{\sqrt{2}}+\cdots+\frac{1}{\sqrt{k}} +\sqrt{k+1}-\sqrt{k} \leq \frac{1}{\sqrt{1}}+\frac{1}{\sqrt{2}}+\cdots+\frac{1}{\sqrt{k+1}}$$

agha
  • 10,038