Proving that $\frac{1}{n}+\frac{1}{n+1}+\cdots+\frac{1}{2n}>\frac{13}{24}$ by induction. Where am I going wrong?

Question

I have to prove that $$\frac{1}{n}+\frac{1}{n+1}+\dots+\frac{1}{2n}>\frac{13}{24}$$ for every positive integer $n$.

After I check the special cases $n=1,2$, I have to prove that the given inequality holds for the $n+1$ case by using the $n$ case. So, I have to prove:

$$\frac{1}{n+1}+\frac{1}{n+2}+\dots+\frac{1}{2n}+\frac{1}{2n+1}+\frac{1}{2n+2}\overset{?}{>}\frac{13}{24}$$

what is equivavlent to

$$\frac{1}{n}+\frac{1}{n+1}+\frac{1}{n+2}+\dots+\frac{1}{2n}+\frac{1}{2n+1}+\frac{1}{2n+2}\overset{?}{>}\frac{13}{24}+\frac{1}{n}$$

By using the $n$ case, I know that

$$\frac{1}{n}+\frac{1}{n+1}+\frac{1}{n+2}+\dots+\frac{1}{2n}+\frac{1}{2n+1}+\frac{1}{2n+2}>\frac{13}{24}+\frac{1}{2n+1}+\frac{1}{2n+2}$$

so I basically have to prove that

$$\frac{13}{24}+\frac{1}{2n+1}+\frac{1}{2n+2}\overset{?}{>}\frac{13}{24}+\frac{1}{n}$$

what is equivavlent to

$$\frac{1}{2n+1}+\frac{1}{2n+2}\overset{?}{>}\frac{1}{n}$$

$$n(2n+2)+n(2n+1)\overset{?}{>}(2n+1)(2n+2)$$

$$4n^2+3n\overset{?}{>}4n^2+6n+2$$

$$-3n\overset{?}{>}2$$

$$n\overset{?}{<}-\frac{2}{3}$$

which can not be because $n$ is a positive integer. What am I doing wrong? Tnx!

Answer 1

You haven't done anything wrong. The thing is, what you have done is just check one possible approach to proving the result, and found that it doesn't work. Where you said

so basically I have to prove that

it would have been a bit more precise to say

so it would be enough to prove that

That was correct — it would be enough — but unfortunately, as others have pointed out already, the subsequent statement is not true.

---

To repair a proof by induction in this kind of situation, a common technique is strengthening the inductive hypothesis. To review: you tried to prove $$ \forall n\quad\colon\quad a_n > \frac{13}{24} \implies a_n + \frac1{2n+1} + \frac1{2n+2} - \frac1n > \frac{13}{24} $$ but found that the assumption $a_n > \frac{13}{24}$ is not strong enough to prove the desired conclusion $a_n + \frac1{2n+1} + \frac1{2n+2} - \frac1n > \frac{13}{24}$. (Maybe this point is clearer if written this way: the assumption $x>\frac{13}{24}$ is not strong enough to prove the desired conclusion $x + \frac1{2n+1} + \frac1{2n+2} - \frac1n > \frac{13}{24}$.) So, what if we had a stronger assumption? Maybe we can give a proof by induction, not of $a_n>\frac{13}{24}$, but of some stronger statement $$ \forall n\quad\colon\quad a_n > \frac{13}{24} + b_n $$ We don't know yet what $b_n$ should be, but what we hope will happen is that the inductive proof of this statement will go through. That is, we hope to be able to show that $$ \forall n\quad\colon\quad a_n > \frac{13}{24} + b_n \implies a_{n+1} > \frac{13}{24} + b_{n+1} $$ How would the inductive step look then? Using the definition of $a_n$, we get, as before, the equivalent project $$ \forall n\quad\colon\quad a_n > \frac{13}{24} + b_n \implies a_n + \frac1{2n+1}+\frac1{2n+2}-\frac1n > \frac{13}{24} + b_{n+1} $$ It would, as before, be enough to show that $$ \forall n\quad\colon\quad \frac{13}{24} + b_n + \frac1{2n+1}+\frac1{2n+2}-\frac1n > \frac{13}{24} + b_{n+1} $$ or equivalently, $$ \forall n\quad\colon\quad b_n + \frac1{2n+1}+\frac1{2n+2}-\frac1n > b_{n+1} $$ So this is a condition that the sequence $b_n$ should satisfy, to let the inductive step work. We just need to choose some sequence $b_n$ satisfying this condition.

You can probably proceed more methodically, but the first thing I tried at this point was $b_n=\frac1n$, just because it's simple and it looks nice that it'll cancel the negative on the LHS, and if it happens to work, we can all go home early. It turns out it does work.

---

Strengthening the inductive hypothesis as above is a widely applicable technique. For this particular problem, an alternative and kind of fancy method is to use the identity $$ \frac1{n+1}+\frac1{n+2}+\dotsb\frac1{n+n} = \frac11 - \frac12 + \frac13 - \frac14 + \dotsb - \frac1{2n} $$ (which is sometimes called Catalan's identity, and which is a good exercise in itself). Since the sum on the RHS is alternating and its terms decrease in absolute value, the partial sums alternately bound the entire sum above and below; in particular, $$ \frac1{n+1}+\frac1{n+2}+\dotsb\frac1{n+n} \ge \frac11 - \frac12 + \frac13 - \frac14 $$ if $n\ge 2$. Thus, if $n\ge 2$, $$ \frac1n + \frac1{n+1}+\frac1{n+2}+\dotsb\frac1{n+n} \ge \frac1n + \frac11 - \frac12 + \frac13 - \frac14 = \frac1n + \frac7{12} > \frac7{12} > \frac{13}{24} $$

Answer 2

Let $$ A_n = \frac{1}{n}+\frac{1}{n+1}+\ldots+\frac{1}{2n}=H_{2n}-H_{n-1}.\tag{1}$$ Then: $$ A_n-A_{n+1} = \frac{1}{n}-\frac{1}{2n+1}-\frac{1}{2n+2}>0 \tag{2} $$ hence the sequence $\{A_n\}$ is decreasing and to prove our claim it is enough to show that: $$ \lim_{n\to +\infty}A_n >\frac{13}{24}=0.541666\ldots.\tag{3}$$ However, by a Riemann sum argument: $$ \lim_{n\to +\infty}A_n = \lim_{n\to +\infty}\frac{1}{n}\left(\frac{1}{1}+\frac{1}{1+\frac{1}{n}}+\frac{1}{1+\frac{2}{n}}+\ldots+\frac{1}{2}\right)\\=\int_{1}^{2}\frac{dx}{x}=\log 2=0.69314718\ldots\tag{4}$$ and we are done. We may also notice that from the upper bound: $$ A_n-A_{n-1} = \frac{2+3n}{2n(n+1)(2n+1)}\leq\frac{3}{(2n)(2n+1)}\tag{5}$$ it follows that: $$ A_n \geq \frac{3}{2}-\sum_{n\geq 1}\frac{3}{(2n)(2n+1)}=\log 8-\frac{3}{2}=0.579441\ldots\tag{6}$$ without using any integral.

Answer 3

As I see it, here's what might be confusing you:

If you let

$$A=\frac{1}{n}+\frac{1}{n+1}+\frac{1}{n+2}+\dots+\frac{1}{2n}+\frac{1}{2n+1}+\frac{1}{2n+2},$$

and

$$B=\frac{13}{24}+\frac{1}{n},$$

then you are trying to prove that $A>B$. Also, if you let

$$C=\frac{13}{24}+\frac{1}{2n+1}+\frac{1}{2n+2},$$

then you have by assumption that $A>C$. Thus if you can prove that $C>B$, as you write yourself, then your are finished, since this will imply that $A>B$.

The problem with this however is that $C\not > B$. This is why you get a contradiction, when you try to prove it, and there's nothing wrong with this. We can have both $A>B$ and $A>C$ without $C>B$.

Answer 4

At first sight it seems to be false because 1/n tends to 0. But I trust you so your inequality is nice. Want I want to remark is you have at hand a pretty proof that the harmonic series is divergent (You have an infinity of "packages" each of them greater than 13/24)