# 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

-
What about $n=0\;$? $\frac10<\frac{25}{36}\;$? – draks ... Oct 5 '12 at 11:04
Welcome to math.SE: since you are new, I wanted to let you know a few things about the site. In order to get the best possible answers, it is helpful if you say in what context you encountered the problem, and what your thoughts on it are; this will prevent people from telling you things you already know, and help them give their answers at the right level. – Noah Snyder Oct 5 '12 at 11:14
The sum in the question is the difference of two harmonic numbers $H_{2n}-H_{n}$. Given the asymptotics of $H_n$, it seems that $H_{2n}-H_{n}$ converges to $\ln 2$. Note $25/36 \approx 0.694$ and $\ln 2 \approx 0.693$. – lhf Oct 5 '12 at 12:27
I like this question. (+1) – I'm an artist Oct 5 '12 at 15:43
@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. – TonyK Oct 5 '12 at 19:53

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

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

-
Nice. (Though I would argue that mine requires induction in places, even though it’s not strictly speaking a proof by induction!) – Brian M. Scott Oct 5 '12 at 22:53
Your idea is very good, I am inspired.Thank you very much for everyone's help. Computer help is useful role. But it seems that you can not seem to. To permit a strengthening proposition: ${{S}_{n}}=\frac{1}{n+1}+\frac{1}{n+2}+\ldots +\frac{1}{2n}+\frac{1}{4(n+1)}<\frac{25}{36}$， ${{S}_{n+1}}-{{S}_{n}}=\frac{1}{2n+1}+\frac{1}{2n+2}-\frac{1}{n+1}+\frac{1}{4(n+‌​2)}-\frac{1}{4(n+1)}<-\frac{1}{8{{n}^{3}}+12{{n}^{2}}+4n}$ – geometryscience Oct 6 '12 at 2:43
@geometryscience: I don't understand the sentence "But it seems that you can not seem to."; please rephrase. I don't know why you put $4(n+1)$ instead of $4(n-1)$, but anyway, that last inequality is wrong; that expression is positive (computation). – joriki Oct 6 '12 at 4:26
@joriki: Sorry, I miscalculated.Very grateful for your help – geometryscience Oct 6 '12 at 6:15
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 :-) – TonyK Oct 7 '12 at 11:57

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.

-
small edit , I think you meant $t_3 = 7/12$ in the last inequality. – Vishesh Oct 5 '12 at 11:45
I've removed my comments and will remove this one soon... You'll probably want to remove your replies to them. – lhf Oct 5 '12 at 16:09
See my answer for a proof using a more elementary hammer :-) – joriki Oct 5 '12 at 22:46
See my answer for a proof involving a toothpick :-) – TonyK Oct 9 '12 at 20:31
@TonyK: Very nice indeed. – Brian M. Scott Oct 10 '12 at 0:07

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

-
Very nice indeed! – joriki Oct 7 '12 at 11:14
@joriki: Thank you! And I've managed to slim it down a bit. – TonyK Oct 7 '12 at 11:46

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

-
You may also use the integral way to work it out fast. – I'm an artist Oct 5 '12 at 15:58

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

-
I'd be interested to know whether you'd count the proof in my answer as a genuine inductive proof :-) – joriki Oct 5 '12 at 22:40
@joriki: Of course. After I had posted my answer something of the kind flashed through my mind, too, but I dismissed it at once, as the available space seemed so small. You had to push the start of the induction up to $n=16$ to make it work. – Christian Blatter Oct 6 '12 at 8:10
Surprisingly, TonyK suceeded in starting the induction at $n=2$. – joriki Oct 10 '12 at 17:55

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

-

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

-
In the last step, isn't it enough to argue that the integral is positive and so $a_n < \ln 2$ ? – lhf Oct 5 '12 at 19:18

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.

-
Unfortunately $\frac1{2n+1}+\frac1{2n+2}-\frac1{n+1}=\frac1{2n+1}-\frac1{2n+2}=\frac1{(2n+1)(2‌​n+2)}>0$ for all $n>0$. In fact you could have guessed there is a problem since you never use anything about $\frac{25}{36}$ except that it is at least $\frac12$. (And in your last step you should switch the operands of "$<$", which makes the resulting statement false.) – Marc van Leeuwen Oct 5 '12 at 12:45
I see the mistake - I was a bit too hasty in the last step. Thanks for pointing out! – Martin Oct 5 '12 at 13:01