14
$\begingroup$

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

by Mathematical induction,n$\ge $1

  • 2
    @draks: the implied sum (even before the edit) was obviously over $n+1 \le i \le 2n$. If $n$ is zero, this implied sum is empty, thus no division by zero.2012-10-05

8 Answers 8

9

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.

  • 0
    My proof (see below) is similar, but I managed to use $4n+1$ instead of your $4(n−1)$. So I only need to compute two terms, not sixteen :-)2012-10-07
6

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.

  • 0
    @TonyK: Very nice indeed.2012-10-10
6

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$.

  • 0
    @joriki: Thank you! And I've managed to slim it down a bit.2012-10-07
1

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

See my answer here.

  • 0
    You may also use the integral way to work it out fast.2012-10-05
1

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})$.

  • 0
    Surprisingly, TonyK suceeded in starting the induction at $n=2$.2012-10-10
0

EDIT: I didn't use induction, my bad :P

I'll provide an analytical approach, but I won't verify every detail so the solution might be false. We try prove $\sum^n_{i=1} \frac 1 {n+1}$.

My first approach was to take the upper bound for each summand, which failed because the resulting sum is $\frac n {n+1}$. So I wanted to find a tighter inequality. I chose

$ \sum^n_{i=1} \frac 1 {n+1} = \sum^{2n}_{i=n+1} \frac 1i \overset{!}\leq \int_n^{2n}\frac 1x dx = \ln(2n) - \ln(n) = \ln(2) + \ln(2) - \ln(2) = \ln(2)$

Now we need to show $\ln(2) < \frac{25}{36}$. This can be done using the series expansion of $\exp$.

0

I didn't prove it by mathematical induction.

Set $a_{n}=\frac{1}{n+1}+\frac{1}{n+2}+\cdots+\frac{1}{2n}$, then by calculation, $a_{n+1}-a_{n}=\frac{1}{2n+1}-\frac{1}{2n+2}$, $a_{n}$ is strictly monotonically increasing.

So we can obtain that

$\begin{align*} a_{n}&=a_{1}+\sum_{k=1}^{n-1}(a_{k+1}-a_{k})\\ &=\frac{1}{2}+\sum_{k=1}^{n-1}(\frac{1}{2k+1}-\frac{1}{2k+2})\\ &=\sum_{k=0}^{n-1}(\frac{1}{2k+1}-\frac{1}{2k+2})\\ &=\sum_{k=0}^{n-1}\int_{0}^{1}(x^{2k}-x^{2k+1})dx\\ &=\int_{0}^{1}\sum_{k=0}^{n-1}(x^{2k}-x^{2k+1})dx\\ &=\int_{0}^{1}\frac{1-x^{2n}}{1+x}dx\\ &=\ln2-\int_{0}^{1}\frac{x^{2n}}{1+x}dx \end{align*}$

When $x\in[0,1]$, $\frac{x^{2n}}{2}\leq\frac{x^{2n}}{1+x}\leq x^{2n}$, integraling at both sides, we can get that $(0<)\frac{1}{2(2n+1)}\leq\int_{0}^{1}\frac{x^{2n}}{1+x}dx\leq\frac{1}{2n+1}$, so for arbitrary $n$, $a_{n}<\ln2<\frac{25}{36}$.

  • 0
    In the last step, isn't it enough to argue that the integral is positive and so a_n < \ln 2 ?2012-10-05
-1

EDIT: This approach is unfortunately wrong, as pointed out in the comments.

Let $S(n) = \frac{1}{ n+1}+\frac{1}{ n+2}+\cdots+\frac{1}{2n}.$

(1) Base step. Let $n=1$. Then $n+1 = 2n$, so the series only has one term. $S(1) = \frac{1}{2} < \frac{25}{36}$, hence the statement is true for $n=1$.

(2) Inductive step. Suppose the induction hypothesis is true. Then

$S(n+1) = \frac{1}{ (n+1)+1}+\frac{1}{ (n+1)+2}+\cdots+\frac{1}{2(n+1)}$

$= \frac{1}{ n+2}+\frac{1}{n+3}+\cdots+\frac{1}{2n} + \frac{1}{2n+1} + \frac{1}{2n+2}$

$= - \frac{1}{n+1} + \left(\frac{1}{n+1} + \frac{1}{ n+2}+\frac{1}{n+3}+\cdots+\frac{1}{2n}\right) + \frac{1}{2n+1} + \frac{1}{2n+2}$

$= - \frac{1}{n+1} + \frac{1}{2n+1} + \frac{1}{2n+2} + S(n)$

$< - \frac{1}{n+1} + \frac{1}{2n+1} + \frac{1}{2n+2} + \frac{25}{36}$

where the inequality comes from the induction hypothesis.

Now $S(n+1) < \frac{25}{36}$, as we want to show, requires $- \frac{1}{n+1} + \frac{1}{2n+1} + \frac{1}{2n+2} < 0.$

As $- \frac{1}{n+1} + \frac{1}{2n+1} + \frac{1}{2n+2} < - \frac{1}{n+1} + \frac{1}{2n+1} + \frac{1}{2n+1}$, this is certainly true if

$- \frac{1}{n+1} + \frac{1}{2n+1} + \frac{1}{2n+1} < 0$, or $\frac{1}{n+1} < \frac{2}{2n+1}$. The last inequality is trivial to show.

  • 0
    I see the mistake - I was a bit too hasty in the last step. Thanks for pointing out!2012-10-05