prove $\frac{1}{ n+1}+\frac{1}{ n+2}+\cdots+\frac{1}{2n}<\frac{25}{36}$ by mathematical induction

How to prove $$\frac{1}{ n+1}+\frac{1}{ n+2}+\cdots+\frac{1}{2n}<\frac{25}{36}$$

by Mathematical induction，n$\ge $1

Solution 1:

As far as I can tell, none of the answers so far gives a proof by induction. Here's one.

Let

$$S_n=\sum_{k=n+1}^{2n}\frac1k\;.$$

By explicit computation

$$\frac{25}{36}-\frac1{60}-S_{16}=\frac{238793353}{20629078984800}\gt0\;.$$

As others have pointed out, the sequence monotonically increases, so this establishes the inequality up to $n=16$. Now we can prove

$$ S_n\lt\frac{25}{36}-\frac1{4(n-1)} $$

for $n\ge16$ by induction. The base case is handled above. The induction step is

$$ \begin{align} S_{n+1} &= S_n+\frac1{2n+1}+\frac1{2n+2}-\frac1{n+1} \\ &= S_n+\frac1{(2n+1)(2n+2)} \\ &\lt S_n+\frac1{4n(n-1)} \\ &\lt \frac{25}{36}-\frac1{4(n-1)}+\frac1{4n(n-1)} \\ &= \frac{25}{36}-\frac1{4n}\;. \end{align} $$

The general insight to be gained here is that a proof by induction sometimes becomes easier when we make the conclusion stronger. That's because this not only strengthens the conclusion of the induction step but also its premise. In the present case, the original claim can't be proved directly by induction, since knowing that the inequality holds doesn't help in proving that it holds if we add something to the lesser side; but by strengthening the conclusion slightly more for $n$ than for $n+1$ we can create some space to work with in the induction step.

Solution 2:

Here’s one approach to the problem. It’s entirely possible that there’s a shorter, slicker solution to this particular problem, but I thought that it might be helpful to explain my thought processes in solving it as an illustration of how one might attack such a problem. I’ve still left quite a bit of work for you to fill in.

Let $$s_n=\frac1{n+1}+\frac1{n+2}+\ldots+\frac1{2n}$$ for $n\ge 1$; the problem is to show that $s_n<\frac{25}{36}$ for all $n\ge 1$. A little calculation shows that $s_1=\frac12,s_2=\frac7{12}$, and $s_3=\frac{37}{60}$, so it appears that the sequence is increasing. Since the righthand side of the desired inequality is constant, $\frac{25}{36}$, the sequence can’t be increasing very quickly; it might be a good idea to see just how much it increases with each term.

$$\begin{align*} s_{n+1}-s_n&=\left(\frac1{n+2}+\frac1{n+3}+\ldots+\frac1{2n+2}\right)-\left(\frac1{n+1}+\frac1{n+2}+\ldots+\frac1{2n}\right)\\ &=\frac1{2n+1}+\frac1{2n+2}-\frac1{n+1}\\ &=\frac1{2n+1}-\frac1{2n+2}\;. \end{align*}$$

Thus,

$$\left\{\begin{align*}s_1&=\frac12\;,\\ s_2&=s_1+(s_2-s_1)=\frac12+\frac13-\frac14\;,\\ s_3&=s_2+(s_3-s_2)=\frac12+\frac13-\frac14+\frac15-\frac16\;, \end{align*}\right.\tag{1}$$

and so on. You should be able to prove a generalization of $(1)$ fairly easily by induction.

Now notice that in each line of $(1)$, the series on the right is alternating except for the first term, and the terms are decreasing. Consider the infinite series

$$\frac12+\frac13-\frac14+\frac15-\frac16+\frac17-\frac18\pm\ldots\;,\tag{2}$$

and let $t_n$ be the $n$-th partial sum: $t_1=\frac12$, $t_2=\frac12+\frac13$, $t_3=\frac12+\frac13-\frac14$, and so on. Notice that $s_n=t_{2n-1}$ for every $n\ge 1$.

Corrected: At this point I recognize a familiar series and get out a moderately heavy hammer:

$$\ln 2=\sum_{n\ge 1}\frac{(-1)^{n+1}}n=1-\frac12+\frac13-\frac14\pm\ldots\;,\tag{3}$$ which is exactly the same as $(2)$ after you combine the first two terms. Because $(3)$ is an alternating series with strictly decreasing terms tending to $0$, its partial sums are alternately above and and below its sum, and our terms $s_n$ are precisely the partial sums that are below $\ln 2$, the sum of the series. Since $\ln 2\approx0.69315<0.69\overline{4}=\frac{25}{36}$, we have the desired inequality.

Solution 3:

Here's an elementary proof, that requires no lengthy computations. Let

$$S_n=\sum_{k=n+1}^{2n}\frac1k$$

We show by induction that $S_n \le \frac{25}{36} - \frac{1}{4n+1}$ for all $n \ge 2$. To start with, $S_2 = \frac13+\frac14=\frac{25}{36} - \frac19$, so the hypothesis is true for $n=2$. Now suppose it is true for $n-1$. Then

$$\begin{align} S_n &= S_{n-1} -\frac1n + \frac{1}{2n-1} + \frac{1}{2n}\\ &= S_{n-1} + \frac{1}{2n(2n-1)}\\ &\le \frac{25}{36} - \frac{1}{4n-3} + \frac{1}{2n(2n-1)}\\ &= \frac{25}{36} - \frac{1}{4n+1} - \frac{4}{(4n-3)(4n+1)} + \frac{1}{2n(2n-1)}\\ &< \frac{25}{36} - \frac{1}{4n+1} \end{align}$$ because $2n(2n-1) > (4n-3)(4n+1)/4$.

Solution 4:

Maybe you want to use Botez-Catalan identity and then Taylor expansion of $\ln(1+x)$ at $x=0$.

See my answer here.

Solution 5:

Let $$S_n:={1\over n+1}+\ldots+{1\over 2n}\ .$$ Since $$S_{n+1}-S_n={1\over 2n+1}-{1\over 2n+2}>0$$ I don't think there is a genuine inductive proof of the stated inequality. But we can argue as follows: $$S_n={1\over n}\left({1\over1+{1\over n}} +{1\over1+{2\over n}}+\dotso+{1\over1+{n\over n}}\right)$$ can be regarded as a Riemann sum for the integral $\int_0^1{1\over 1+x}\ dx$, and looking at the graph of the integrand we see that in fact $$S_n<\int_0^1{1\over 1+x}\ dx=\log 2<{25\over36}\ .$$ If desired one could prove the last inequality "from first principles", using the series for $\log(1-{1\over2})$.