Friday, July 11, 2025

Proof Σ(1/√k)[k=1→n] < 2√n

Prove, using induction, that for every natural number n: $$\displaystyle \begin{aligned} 1+\dfrac{1}{\sqrt{2}}+\dfrac{1}{\sqrt{3}}+\cdots +\dfrac{1}{\sqrt{n}}<2\sqrt{n} \end{aligned}$$

Proof by Induction

We are asked to prove that for all natural numbers $n \geq 1$:

$$ 1 + \frac{1}{\sqrt{2}} + \frac{1}{\sqrt{3}} + \cdots + \frac{1}{\sqrt{n}} < 2\sqrt{n} $$

or in summation form:

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


Step 1: Base Case

Check for $n = 1$:

$$ \sum_{k=1}^1 \frac{1}{\sqrt{k}} = \frac{1}{\sqrt{1}} = 1 $$

Check if:

$$ 1 < 2\sqrt{1} \implies 1 < 2 $$

✅ True.


Step 2: Induction Hypothesis

Assume the inequality holds for some $n = k \geq 1$:

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

This is the induction hypothesis.


Step 3: Induction Step

Prove it holds for $n = k+1$:

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

Start from the induction hypothesis:

$$ \sum_{i=1}^{k+1} \frac{1}{\sqrt{i}} = \left( \sum_{i=1}^k \frac{1}{\sqrt{i}} \right) + \frac{1}{\sqrt{k+1}} $$

Apply the hypothesis:

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

We need to show:

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

Subtract $2\sqrt{k}$ from both sides:

$$ \frac{1}{\sqrt{k+1}} < 2\left(\sqrt{k+1} - \sqrt{k}\right) $$

Compute the right-hand side:

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

Then:

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

Check if:

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

Cross multiply (all terms are positive):

$$ \left(\sqrt{k+1} + \sqrt{k}\right) < 2\sqrt{k+1} $$

Check:

$$ \sqrt{k} < \sqrt{k+1} $$

✅ Always true for all $k \geq 1$.


Conclusion:

The induction step holds. Therefore, by the principle of mathematical induction, the inequality

$$ \sum_{i=1}^n \frac{1}{\sqrt{i}} < 2\sqrt{n} $$

holds for all natural numbers $n \geq 1$. ✅

No comments:

Post a Comment