Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

by Mathematical induction,n$\ge $1

share|improve this question
5  
What have you tried? –  Patrick Li Oct 5 '12 at 10:57
    
What about $n=0\;$? $\frac10<\frac{25}{36}\;$? –  draks ... Oct 5 '12 at 11:04
2  
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. If this is homework, please add the homework tag; people will still help, so don't worry. Also, many find the use of imperative "Prove" to be rude when asking for help; please consider rewriting your post. –  Noah Snyder Oct 5 '12 at 11:14
3  
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
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. –  TonyK Oct 5 '12 at 19:53
show 1 more comment

8 Answers

up vote 8 down vote accepted

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.

share|improve this answer
    
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
1  
@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
add comment

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.

share|improve this answer
    
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
1  
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
add comment

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.

share|improve this answer
    
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
add comment

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

share|improve this answer
add comment

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

See my answer here.

share|improve this answer
    
You may also use the integral way to work it out fast. –  Chris's sis Oct 5 '12 at 15:58
add comment

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

share|improve this answer
    
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
add comment

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

share|improve this answer
    
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
add comment

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

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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