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.

Thanks to How to use mathematical induction with inequalities? I can now work with some induction problems related to inequalities. I've been following the logic that I was presented there so far.

Until for $n\ge1$, I had to prove the following: $$\frac{1}{n+1}+\frac{1}{n+2}+\cdots+\frac{1}{n+(n+1)}\le\frac{5}{6}$$ Unlike the last time, now I have a constant $\frac{5}{6}$ at the right side. Maybe it makes no difference, so despite that I decided to try it anyway with pretty much the same procedure that André Nicolas used in How to use mathematical induction with inequalities?:

The inequality holds for $n=1$. We now assume the following: $$\frac{1}{n+1}+\frac{1}{n+2}+\cdots+\frac{1}{n+(n+1)}\le\frac{5}{6}$$ We want to prove that it holds for $n+1$, so we'd like to show this: $$\frac{1}{n+1}+\frac{1}{n+2}+\cdots+\frac{1}{n+(n+1)}+\frac{1}{(n+1)+(n+2)}\le\frac{5}{6}$$ (So something different happened since last time: the right side did not change at all. It worried me, but since I'm just following the same steps I always do I will leave it like that and see what happens).

By the induction assumption we can say that $$\frac{1}{n+1}+\frac{1}{n+2}+\cdots+\frac{1}{n+(n+1)}+\frac{1}{(n+1)+(n+2)}\le\frac{5}{6}+\frac{1}{(n+1)+(n+2)}$$

We will be finished if we can show that $$\frac{5}{6}+\frac{1}{(n+1)+(n+2)}\le\frac{5}{6}$$

.... Oh wait. That's impossible! (I guess)


I guess that it is because the right side remained unchanged back then. But well, in that case, I'm not sure how should I do it then. My question then: how would I solve mathematical induction problems with inequalities that have a constant in the right side?

share|improve this question
    
In going from $n$ to $n+1$, you add stuff on the right, but, very importantly, you lose something on the left. –  André Nicolas Nov 28 '12 at 0:30
    
@AndréNicolas: I lose something?... Hmm, well, now that I look at it (and after the corrections I was told recently), you mean the $\frac{1}{n+1}$? It seems to be gone from the left side... so I should be adding it to the right then? –  Zol Tun Kul Nov 28 '12 at 0:37
    
It was well explained well in Henry's answer. The sum for $n+1$ is the sum for $n$, plus $\frac{1}{(n+1)+(n+1)}+\frac{1}{(n+1)+(n+2)}$ minus $\frac{1}{n+1}$. But the stuff we added is a little smaller than the stuff we subtracted, so actually the sum for $n+1$ is less than the sum for $n$. To get concrete control of things, calculate the sum when $n=1$. Then do it for $n=2$, and maybe $n=3$. –  André Nicolas Nov 28 '12 at 0:44

3 Answers 3

up vote 4 down vote accepted

You actually want to show

$$\frac{1}{n+2}+\frac{1}{n+3}+\cdots+\frac{1}{(n+1)+(n+1)}+\frac{1}{(n+1)+(n+2)}\le\frac{5}{6}$$

So you take the inductive hypothesis, and subtract $\frac{1}{n+1}$ from and add $\frac{1}{(n+1)+(n+1)}+\frac{1}{(n+1)+(n+2)}$ to the left hand side. Since you can show that change is less than zero, the overall sum is still less than or equal to $\frac56$.

share|improve this answer

When you say "What we want to prove is ...", you're actually wrong, you have to "update" the $n$ to $n+1$ on every fraction, not only the one you add.

share|improve this answer

Hint $\ \ $ If $\rm\ \ f(n) =\, \dfrac{5}6 - \dfrac{1}{n\!+\!1} - \dfrac{1}{n\!+\!2} - \,\cdots\, - \dfrac{1}{2n\!+\!1}\ $ then $$\rm f(n\!+\!1)-f(n) = \dfrac{1}{n\!+\!1}-\dfrac{1}{2n\!+\!2}-\dfrac{1}{2n\!+\!3} = \dfrac{1}{2(n\!+\!1)(2n\!+\!3)} > 0$$

thus $\rm\:f(n)\:$ is increasing, so $\rm\:f(n) \ge \cdots \ge f(1) \ge f(0) = \frac{5}6\!-\!\frac{1}2\!-\!\frac{1}3 = 0\:$ by induction.

Remark $\ $ In the same way, one can often reduce inductive proofs to trivial inductions, such as the above induction that an increasing function stays $\ge$ its initial value. For further discussion and examples see my many prior posts on telescopy. There, you'll learn that, by summing, the above proof can be viewed as a trivial induction that a sum of nonnegative integers stays nonnegative. The sooner one learns how to restructure inductive proofs to make the induction "obvious", the sooner one will be able to tackle much more complicated inductions that arise in the wild.

share|improve this answer

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.