Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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
add comment

2 Answers

up vote 1 down vote accepted

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.

share|improve this answer
add comment

$$\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}$$

share|improve this answer
    
Ohh... I see it, thank you –  fdhd Nov 5 '12 at 14:11
1  
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.