# Induction inequality on sum of reciprocals

I have to prove that: $\displaystyle\frac{1}{n}+\frac{1}{n+1}+...+\frac{1}{2n}\ge\frac{1}{2}$ for natural $n$

Checking for $n=1$ we have $\displaystyle 1+\frac{1}{2}=\frac{3}{2}\ge \frac{1}{2}$

Next we assume that inequality is true for $n$ and for $n+1$ we have:

$\displaystyle\frac{1}{n}+\frac{1}{n+1}+...+\frac{1}{2n}+\frac{1}{2n+1}\ge\frac{1}{2}+\frac{1}{2n+1}\ge\frac{1}{2}$ what is true because $\displaystyle \frac{1}{2n+1} \ge 0$

Is my proof correct ?

-
Don't think so! :-( –  pushpen.paul Jul 31 '14 at 12:25
In the $n+1$ step, you need the sum $\frac{1}{n+1}+...+\frac{1}{2n+2}$ –  Alex R. Jul 31 '14 at 12:25

Take a look at the first few cases to get an idea what should happen. The first claim is $\frac11+\frac12\geq\frac12$, the second one is $\frac12+\frac13+\frac14\geq\frac12$, the third one is $\frac13+\frac14+\frac15+\frac16\geq\frac12$.

So to get from $\frac1n+\dots+\frac1{2n}$ to $\frac1{n+1}+\dots+\frac1{2(n+1)}$ you need to subtract $\frac1n$ and add $\frac1{2n+1}+\frac1{2n+2}$. Thus the difference of the adjacent sums is $\frac1{2n+1}+\frac1{2n+2}-\frac1n=-\frac{3n+2}{n(2n+1)(2n+2)}$. This is negative, so the sum keeps getting smaller as $n$ grows. Therefore such an induction cannot work.

A proof without induction is easier: Your sum has $n+1$ terms and the smallest one is $\frac1{2n}$. Thus the sum is at least $(n+1)\times\frac1{2n}=\frac{n+1}{2n}>\frac12$.

-
A tiny point. I suspect that your calculation would be wrong...in front of 'This is negative' –  mathlove Jul 31 '14 at 12:41
@mathlove Thanks. I made an edit. –  Joonas Ilmavirta Jul 31 '14 at 12:43
what if there will be $\frac{7}{12}$ instead of $\frac{1}{2}$ ? using this method we will obtain $\frac{1}{2n}\ge\frac{1}{12}$ –  Gregor Jul 31 '14 at 12:51
@Gregor I don't quite understand your question. Do you mean a specific value of $n$? And where would the $\frac7{12}$ appear instead of $\frac12$? –  Joonas Ilmavirta Jul 31 '14 at 12:58
I mean such situation: $\displaystyle \frac{1}{n}+\frac{1}{n+1}+...+\frac{1}{2n} \ge \frac{7}{12}$ to show that it's satisfied for all natural numbers –  Gregor Jul 31 '14 at 13:00

The proof is nearly correct, but induction is unnecesary:

$$\frac{1}{n} + \frac{1}{n+1} +\ldots + \frac{1}{2n} \geq \underbrace{\frac{1}{2n} + \frac{1}{2n}+\ldots +\frac{1}{2n} \frac{1}{2n}}_{n\text{ times}} = n\frac{1}{2n} = \frac{1}{2}$$

-
(+1) quick and sharp! –  Alex Jul 31 '14 at 14:35
@Alex That's what she said! –  Darth Geek Jul 31 '14 at 14:42