0

So far I have this. I have a feeling I'm getting off track with the last two steps.

We want to prove $\sum_{i=1}^{n} \frac{1}{\sqrt{i}}$ $< 2\sqrt{n}$ for $n \geq 1$

Base Case

Prove P(1): $\sum_{i=1}^{1} \frac{1}{\sqrt{1}}$ $< 2\sqrt{1}$. We get $1 < 2$.

Induction Hypothesis

$\sum_{i=1}^{n} \frac{1}{\sqrt{n}}$ $< 2\sqrt{n}$ is true for $n \geq 1$

Induction Step

Prove P(k + 1): $\sum_{i=1}^{k + 1} \frac{1}{\sqrt{k + 1}} < 2\sqrt{k + 1} $

LHS = $\sum_{i=1}^{k + 1} \frac{1}{\sqrt{k + 1}}$

= $\sum_{i=1}^{k} \frac{1}{\sqrt{k}}$ - 1 + $\frac{1}{\sqrt{k + 1}}$ + $\frac{1}{\sqrt{k + 2}}$

$< 2\sqrt{k}$ - 1 + $\frac{1}{\sqrt{k + 1}}$ + $\frac{1}{\sqrt{k + 2}}$

2 Answers2

1

Hint: $$2(\sqrt{n+1}-\sqrt n)=\frac2{\sqrt{n+1}+\sqrt n} $$

Hagen von Eitzen
  • 374,180
0

You should only be doing induction on $n$, not changing the index $i$ as well. We only want to show that this holds if we add the first $n$ terms of the series. For example, your induction hypothesis should read $$\sum_{i=1}^n \frac{1}{\sqrt{i}}=\frac{1}{\sqrt{1}} + \frac{1}{\sqrt{2}} + \cdots + \frac{1}{\sqrt{n}}$$ instead of $$\sum_{i=1}^n \frac{1}{\sqrt{n}} = \frac{1}{\sqrt{n}} + \frac{1}{\sqrt{n}} + \cdots + \frac{1}{\sqrt{n}}$$

Similar story for when you do the induction step, which has the additional complication of switching from $n$ to $k$. Your induction step should read: $$\sum_{i=1}^{n+1} \frac{1}{\sqrt{i}} = \frac{1}{\sqrt{1}} + \frac{1}{\sqrt{2}} + \cdots + \frac{1}{\sqrt{n}} + \frac{1}{\sqrt{n+1}}$$

How can we use our induction hypothesis to bound this?

erfink
  • 5,287
  • 16
  • 34