2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Namaste Nov 5 '12 at 14:10
1
$\begingroup$

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.

$\endgroup$
6
$\begingroup$

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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