Discrete Math Proof Question Inductive Proof

Question

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)

Answer 1

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...

Answer 2

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.