Induction: show that $1 + \frac{1}{\sqrt{2}} + \frac{1}{\sqrt{3}} + \frac{1}{\sqrt{4}} + ... + \frac{1}{\sqrt{n}} < 2\sqrt{n}$

Question

The question:

Induction: show that: $$1 + \frac{1}{\sqrt{2}} + \frac{1}{\sqrt{3}} + \frac{1}{\sqrt{4}} + ... + \frac{1}{\sqrt{n}} < 2\sqrt{n}$$

for $n \geq 1$

My attempt at a solution:

First we test the base case: $n=1$ this gives us:

$$1 < 2$$

Which works.

Then we do the inductive assumption that it holds true for $k=n$, this gives us:

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

If we can prove that the following is true, we have solved the problem:

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

we then have to show that $$2\sqrt{n} + \frac{1}{\sqrt{n+1}} \leq 2\sqrt{n+1}$$

Which can be written as: $$2\sqrt{n}\sqrt{n+1} + 1 \leq 2(n+1)$$

$$1 \leq 2(n+1) - 2\sqrt{n}\sqrt{n+1}$$

$$2\sqrt{n}\sqrt{n+1} \leq 2(n+1) - 1$$

$$2\sqrt{n}\sqrt{n+1} \leq 2n+1$$

$$(2\sqrt{n}\sqrt{n+1})^2 \leq (2n+1)^2$$

$$4n^2 + 4n \leq 4n^2 + 4n + 1$$

Can anyone please help me to continue from here or does this mean that I have proved the inductive assumption?

Thank you!

Substract $4n^2+4n$ from both side from the last equation. The new equation $0 \leq 1$ is always true — Thomas Produit, Jan 27 '14 at 17:58

score 6 · Accepted Answer · edited Jan 27 '14 at 18:03

6

You have proved it; you just need to write the 6 inequalities in the reverse order, and connect them by implication $\implies$ or keep the ordering and show that each is equivalent $\iff$ with the next.

edited Jan 27 '14 at 18:03

not all wrong

16,178
2
35
57

answered Jan 27 '14 at 17:58

Hoda

1,098

Thank you for your answer and for your clarification! – Lukas Arvidsson Jan 27 '14 at 18:57

score 1 · Answer 2 · answered Jan 27 '14 at 18:24

You have proved it but if you dislike switching to (essentially) showing a new inequality is true you could approach this slightly differently.

$\begin{align} 1 + \frac{1}{\sqrt{2}} + ... + \frac{1}{\sqrt{n+1}} &< 2\sqrt{n} + \frac{1}{\sqrt{n+1}} \mathrm{(by\ inductive\ hypothesis)} \\ &= \frac{2\sqrt{n}(n+1)}{n+1} + \frac{\sqrt{n+1}}{n+1} \\ &= \frac{(2\sqrt{n}\sqrt{n+1}+1)\sqrt{n+1}}{n+1} \\ &= \frac{(2\sqrt{n^2+n}+1)\sqrt{n+1}}{n+1} \\ &< \frac{(2\sqrt{n^2+n+\frac{1}{4}}+1)\sqrt{n+1}}{n+1} \\ &= \frac{(2\sqrt{(n+\frac{1}{2})^2}+1)\sqrt{n+1}}{n+1} \\ &= \frac{(2(n+\frac{1}{2})+1)\sqrt{n+1}}{n+1} \\ &= \frac{(2n+1+1)\sqrt{n+1}}{n+1} \\ &= \frac{(2n+2)\sqrt{n+1}}{n+1} \\ &= \frac{2(n+1)\sqrt{n+1}}{n+1} \\ &= 2\sqrt{n+1} \\ \end{align}$

Thank you for your answer! Much appreciated, will study this! — Lukas Arvidsson, Jan 27 '14 at 19:10

Induction: show that $1 + \frac{1}{\sqrt{2}} + \frac{1}{\sqrt{3}} + \frac{1}{\sqrt{4}} + ... + \frac{1}{\sqrt{n}} < 2\sqrt{n}$

2 Answers2

Linked