# Tricky series inequality proof by induction involving square roots

Prove by induction that

$$1+\frac{1}{\sqrt{2}}+\frac{1}{\sqrt{3}}+...+\frac{1}{\sqrt{n}}<\sqrt{n}, (n\ge2)$$

Induction basis is correct: $$\frac{1}{\sqrt{2}}<\sqrt{2}$$

So we need to prove that $$1+\frac{1}{\sqrt{2}}+\frac{1}{\sqrt{3}}+...+\frac{1}{\sqrt{n}}+\frac{1}{\sqrt{n+1}}<\sqrt{n+1}$$

One of my attempts was to replace $1+\frac{1}{\sqrt{2}}+\frac{1}{\sqrt{3}}+...+\frac{1}{\sqrt{n}}$ by a number that we know from the induction hypothesis to be greater than it, which is $\sqrt{n}$, and if we show that the inequality is still true then we prove the initial statement.

$$\sqrt{n}+\frac{1}{\sqrt{n+1}}\overset{?}{<}\sqrt{n+1}$$

And, unfortunately, the inequality doesn't hold. I checked it in Wolfram Alpha and the difference between one side of the inequality and the other is really really small. In my opinion, that is why this inequality is so tough to prove (for me, obviously).

• $\sqrt{n+1} - \sqrt{n} = \frac{1}{\sqrt{n+1}+\sqrt{n}}$, which is unfortunately smaller than $\frac{1}{\sqrt{n+1}}$ – xyzzyz Nov 8 '16 at 0:40

The inequality is not true: $$1+\frac1{\sqrt2}\simeq1.707>1.4142\simeq\sqrt2.$$ The reverse inequality can be proved by induction, as you are trying: the inductive step would be $$\sqrt n+\frac1{\sqrt{n+1}}>\sqrt{n+1}.$$ This can be seen as follows: from $n+1>n$, we get $$n(n+1)>n^2.$$ Taking square root and adding $1$, $$\sqrt{n(n+1)}+1>n+1.$$ Now divide by $\sqrt{n+1}$: $$\sqrt{n}+\frac1{\sqrt{n+1}}>\sqrt{n+1}.$$

• Because of this problem I though that $n\le2$ meant summing elements of the series only from the $n=2$ element onwards... thanks for pointing out my mistake. And the problem writer's mistake. – Martijon Nov 8 '16 at 10:54
• It says $n\geq2$ because the inequality fails for $n=1$: when $n=1$, it reads $1 <1$. – Martin Argerami Nov 8 '16 at 13:13

Your base case is wrong. The inequality has an opposite sign. It is easy to prove it by induction once you try to prove the right thing.

The induction step is incorrect. Infact, the reverse inequality holds for this question, and the proof of that is simple:

Inductive case: For $n=1$, $1 \geq \sqrt{1}$ is true.

Now, note that if $\displaystyle\sum_{i=1}^k \frac 1 {\sqrt i} \geq \sqrt{k}$ is given, then we have: $$\frac{1}{\sqrt{1+k}} \geq \frac {1}{\sqrt{k} + \sqrt{k+1}} \geq \sqrt{k+1}-\sqrt{k}$$

Simply add the above two inequalities, we get: $$\displaystyle\sum_{i=1}^{k+1} \frac 1 {\sqrt i}=\displaystyle\sum_{i=1}^k \frac 1 {\sqrt i} + \frac{1}{\sqrt{k+1}}\geq \sqrt{k} + (\sqrt{k+1}-\sqrt{k}) \geq \sqrt{k+1}$$

Hence, the reverse inequality $\displaystyle\sum_{i=1}^{k} \frac 1 {\sqrt i} \geq \sqrt{k}$, for $k \geq 1$, is what holds by induction.

Actually, from the standard comparisons (above and below) of sums and integrals in most calculus books, $$2 \sqrt {n+1} - 2 \; \; < \sum_{k=1}^n \frac{1}{\sqrt k} \leq \; \; 2 \sqrt n - 1.$$ The equality case on the right side holds only for $n=1.$