MathB.in - Share Mathematics with LaTeX and Markdown

Prove that $$\frac{1}{\sqrt{1}} + \frac{1}{\sqrt{2}} + \frac{1}{\sqrt{3}} + \dots + \frac{1}{\sqrt{n}} \le 2\sqrt{n} - 1$$ for every positive integer $n$.
--

We use induction. Let the above statement the called $P(n)$. We wish to prove two things:

1. $P(1)$ is true;
  
  2. $\forall k \in \mathbb{N}, P(k) \implies P(k+1)$ is true.

$P(1)$: $$\frac{1}{\sqrt{1}} \le 2\sqrt{1} - 1 = 1$$ is true.

Lemma: $$\forall k \in \mathbb{N}, 2\sqrt{k + 1} - 2\sqrt{k} \ge \frac{1}{\sqrt{k + 1}}.$$

Proof: It follows trivially that
\begin{align*}
& 2(k + 1) \ge 2k + 1 = (k) + (k + 1) \ge 2\sqrt{k(k+1)} \qquad\text{by AM-GM} \\
&\implies \qquad 2k + 2 \ge 2\sqrt{k(k+1)} + 1 \\
&\implies \qquad 2(k + 1) -2\sqrt{k}\sqrt{k+1} \ge 1 \\
&\implies \qquad 2\sqrt{k + 1} -2\sqrt{k} \ge \frac{1}{\sqrt{k + 1}}
\end{align*}

We assume $P(k)$ for an arbitrary positive integer $k$, so we have $$\frac{1}{\sqrt{1}} + \frac{1}{\sqrt{2}} + \frac{1}{\sqrt{3}} + \dots + \frac{1}{\sqrt{k}} \le 2\sqrt{k} - 1.$$ Thus, we have $$\frac{1}{\sqrt{1}} + \frac{1}{\sqrt{2}} + \frac{1}{\sqrt{3}} + \dots + \frac{1}{\sqrt{k}} + 2\sqrt{k + 1} \le 2\sqrt{k + 1} - 2\sqrt{k} + 2\sqrt{k} - 1,$$ so  $$\frac{1}{\sqrt{1}} + \frac{1}{\sqrt{2}} + \frac{1}{\sqrt{3}} + \dots + \frac{1}{\sqrt{k}} + \frac{1}{\sqrt{k + 1}} \le 2\sqrt{k + 1} - 1.$$

Thus, $P(k) \implies P(k + 1)$.

Mon, 04 Jan 2021 11:01 GMT