0
$\begingroup$

prove that 1/√1 + 1√2+ 1/√3+...+1/√n <= 2√n

Proof by Induction: Let P(n) denote 1/ √1 + 1/ √2 + … + 1/ √n <= 2√n Base Case: n = 1, P(1) = 1/√1 <= 2√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 <= 2√k, p(k) holds true for any integer k

Inductive Step: P(k + 1)) = 1/ √1 + 1/ √2 + … + 1/ √k + 1/ √(k + 1) <= 2√k + 1/√(k+1) √k + √(k+1) <= 2√(k+1) (this is where I got stuck)

$\endgroup$
1
$\begingroup$

Following your work so far, $$\frac{1}{\sqrt{1}} + \cdots + \frac{1}{\sqrt{k}} + \frac{1}{\sqrt{k+1}} \le 2 \sqrt{k} + \frac{1}{\sqrt{k+1}} \overset{?}{\le} 2 \sqrt{k+1}.$$ It remains to prove the inequality with the question mark. It is equivalent to $$\sqrt{\frac{k}{k+1}} + \frac{1}{2(k+1)} \overset{?}{\le} 1.$$ It seems that the left-hand side is an increasing function of $k$ that increases to $1$ as $k \to \infty$.

Unfortunately, a more elementary approach eludes me at the moment...

$\endgroup$
  • 1
    $\begingroup$ Perhaps a more elementary approach? $$\sqrt{\frac{k}{k+1}} + \frac{1}{2(k+1)} \le 1$$ Let $\sin u=\frac1{\sqrt{k+1}}$. (Works since $k\ge0$)$$\cos^2 u+\frac12\sin^2 u\le 1\\1-\frac12\sin^2u\le 1\\\checkmark$$ $\endgroup$ – John Doe May 1 '19 at 2:04
  • $\begingroup$ @JohnDoe Nice, that's a clever way to deal with that left-hand side. $\endgroup$ – angryavian May 1 '19 at 2:16
1
$\begingroup$

You need to note that your goal in the induction step here is to prove

$$\sum_{n=1}^{k+1} \frac{1}{\sqrt n} \le 2\sqrt{k+1}$$

on the premise the induction hypothesis holds. I note this because the way you wrote things feels like you're assuming what you're trying to prove in the first place. In any event, the induction hypothesis gives you that

$$\sum_{n=1}^{k} \frac{1}{\sqrt n} \le 2\sqrt{k}$$

Thus, we can pull out the $(k+1)^{th}$ term of the first sum and invoke that hypothesis:

$$\sum_{n=1}^{k+1} \frac{1}{\sqrt n} = \frac{1}{\sqrt{k+1}}+ \color{blue}{\sum_{n=1}^{k} \frac{1}{\sqrt n}} \le \frac{1}{\sqrt{k+1}} + \color{blue}{2\sqrt{k}}$$

Okay, so we can clearly see one thing: that the result we want comes about if

$$\frac{1}{\sqrt{k+1}} + 2\sqrt{k} \le 2\sqrt{k+1}$$

However, we cannot assume this holds, and have to prove it separately. And we can, but it's a bit of a pain. At the same time it's largely just an exercise in algebra.


Now, we can consider what we ultimately want to prove here:

$$\frac{1}{\sqrt{k+1}} + 2\sqrt{k} \le 2\sqrt{k+1}$$

This holds if and only if

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

which is equivalent to, if we divide by $2$,

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

Do you remember when, in middle school, you'd rationalize the denominator? Strange as it might seem, we do a similar thing in reverse here: we multiply the difference of the roots by their sum and divide by that same sum, as below. We then have a product of the form $(a-b)(a+b)=a^2 - b^2$ on top in particular, which simplifies.

$$\sqrt {k+1} - \sqrt{k} = (\sqrt {k+1} - \sqrt{k}) \cdot \frac{\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}}$$

Thus, the inequality we want holds if and only if

$$\frac{1}{2\sqrt{k+1}} \le \frac{1}{\sqrt {k+1} + \sqrt{k}}$$

Equivalently, taking the reciprocal of both sides,

$$2 \sqrt{k+1} \ge \sqrt {k+1} + \sqrt{k}$$

Note that $2 \sqrt{k+1} = \sqrt{k+1} + \sqrt{k+1}$. Subtracting one of these terms from each side, we then get $\sqrt{k+1} \ge \sqrt{k}$ which obviously holds for all $k \in \Bbb R_0^+$.


What this means is that the inequality we desire holds. That is,

$$\sum_{n=1}^{k+1} \frac{1}{\sqrt n} = \cdots \le \frac{1}{\sqrt{k+1}} + 2\sqrt{k} \le 2\sqrt{k+1}$$

completing the proof.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.