# simple induction, why does it go this way?

I have a simple question involving induction. $$\frac{1}{n}+\frac{1}{n+1}+\cdots+\frac{1}{2n}\geq \frac{1}{2}.$$ I think that this does not go with most common version of induction, because of the $\frac{1}{n}$ at the beginning (am I right?). So here is a need to add something to the right side of inequality and then check whether the statement is still true (how do I guess the term which is to be added?). Mate suggested to add to $\frac{1}{2}$ the $\frac{1}{2n-1}$ term. But why this? Thank you in advance for time and answer.

-
Are you asking how to prove the inequality by induction on n? I.e., assuming it's true for n, and proving it still holds for (n+1) where (n+1) replaces all the occurrences of n? –  amWhy Nov 5 '12 at 14:10

Let $\displaystyle F(n)=\frac1{n+1}+\frac1{n+2}+\dots+\frac1{2n}$, so the sums you want to consider are the numbers $1+F(1)$, $\displaystyle \frac 12+F(2)$, $\displaystyle \frac 13+F(3)$, etc.

Begin by noting that $\displaystyle F(1)=\frac12$. It follows by induction that $\displaystyle F(n)\ge \frac12$ for all $n$, because $$\begin{array}{rcl} F(n+1)&=&F(n)+\frac1{2n+1}+\frac1{2n+2}-\frac1{n+1}\\ &>&F(n)+\frac1{2n+2}+\frac1{2n+2}-\frac1{n+1}\\ &=&F(n). \end{array}$$

Therefore $\displaystyle \frac1n+F(n)>\frac12$ for all $n$, as wanted.

Note that the point here was to give an inductive argument, as you requested, since the inequality itself can be proved quickly as pointed out in another answer: $$\frac1n+\frac1{n+1}+\dots+\frac1{2n}>\frac1{2n}+\frac1{2n}+\dots+\frac1{2n}=\frac{n+1}{2n}>\frac12$$ (which, I suppose, can be argued inductively, in a somewhat awkward way).

What makes finding an inductive argument a bit tricky is that, letting $\displaystyle G(n)=\frac1n+\frac1{n+1}+\dots+\frac1{2n}$, the sequence $G(1)-1/2$, $G(2)-1/2$, $G(3)-1/2$, etc, is decreasing, so knowing that $G(1)=1>0$ does not help us to conclude that $G(n)\ge0$ for all $n$ (or, at least, does not help us directly).

Perhaps paradoxically, the problem becomes easier by replacing $G(n)$ with the smaller quantity $F(n)$, as in the argument above.

-

$$\frac{1}{n}+\frac{1}{n+1}+\ldots +\frac{1}{2n}\geq \frac{1}{2n}+\frac{1}{2n}+\ldots +\frac{1}{2n}=\frac{n+1}{2n}\ge\frac{n}{2n}=\frac{1}{2}$$

-
Ohh... I see it, thank you –  fdhd Nov 5 '12 at 14:11
Isn't it $n+1$ terms? Not that it changes anything... –  N.U. Nov 5 '12 at 14:15
You are right, @N.U. , but then the inequality is even "harsher" as one uses one (positive, of course) fraction less. Thanks. –  DonAntonio Nov 5 '12 at 14:41