Prove Inequality by Mathematical Induction

In summary, the problem you are having is that you are trying to prove a mathematical proposition using induction, and square roots are causing problems. You can solve the problem by using calculus to approximate the roots of the equation, and by using a graph to show that the LHS is always < 0.
  • #1
agent007bond
6
0

Homework Statement



[tex]\forall n \in Z^+, \sum_{i=1}^n \frac{\sqrt{i+1}}{2i} > \frac{\sqrt{n}}{2}[/tex]

Homework Equations



I have to prove the above via mathematical induction.

The Attempt at a Solution



I did the base case, n = 1 and found it true for the base case.

Then I assumed that the proposition is true for n = k: [tex]\sum_{i=1}^k \frac{\sqrt{i+1}}{2i} > \frac{\sqrt{k}}{2}[/tex] ... (1)

Then, when n = k+1, [tex]\sum_{i=1}^{k+1} \frac{\sqrt{i+1}}{2i} > \frac{\sqrt{k+1}}{2}[/tex] ... (2)

The LHS is equivalent to: [tex]\sum_{i=1}^k \frac{\sqrt{i+1}}{2i} + \frac{\sqrt{k+2}}{2k+2}[/tex]

Comparing with equation (1) I can write the following: [tex]\sum_{i=1}^k \frac{\sqrt{i+1}}{2i} + \frac{\sqrt{k+2}}{2k+2} > \frac{\sqrt{k}}{2} + \frac{\sqrt{k+2}}{2k+2}[/tex]

Hence, [tex]\sum_{i=1}^{k+1} \frac{\sqrt{i+1}}{2i} > \frac{\sqrt{k}}{2} + \frac{\sqrt{k+2}}{2k+2}[/tex] ... (3)

According to our lecturer, from (2) and (3) we have: [tex]\sum_{i=1}^{k+1} \frac{\sqrt{i+1}}{2i} > \frac{\sqrt{k}}{2} + \frac{\sqrt{k+2}}{2k+2} > \frac{\sqrt{k+1}}{2}[/tex]

Therefore to prove (2), we need to prove the inequality: [tex]\frac{\sqrt{k}}{2} + \frac{\sqrt{k+2}}{2k+2} > \frac{\sqrt{k+1}}{2}[/tex]

Simplifying it, I can come up with: [tex](k+1)\sqrt{k} + \sqrt{k+2} > (k+1)\sqrt{k+1}[/tex]

How do I prove this inequality (in order to prove the proposition)? Many of my friends in school are also as stuck as I am! Could someone help me?!
 
Physics news on Phys.org
  • #2
Mathematical induction?


Maybe not. Anyways, what is the problem you're having with that inequality? Is it because all of those square roots?

(P.S. is this calculus? If so, that gives you even more options)
 
  • #3
I guess so. For [tex]\frac{\sqrt{k}}{2} + \frac{\sqrt{k+2}}{2k+2} > \frac{\sqrt{k+1}}{2}[/tex], how do I prove that the LHS is greater than the RHS for all positive integers?

(PS: I can use calculus to solve the problem. Could you guide me how to use calculus to solve inequality?)
 
  • #4
Well, if square roots are the problem... don't you know how to get rid of them?
 
  • #5
How do I get rid of them?
If you mean to do squaring both sides, well there is a + sign on LHS, so it's going to get longer and still have a square root.

Also if I move the non-square root terms to the right side and square the equation again, it's going to get much longer and more complicated.

Actually I tried this already and came up with a string of powers of k > another string of powers of k. Still can't prove anything.

Is it possible to use calculus?
 
Last edited:
  • #6
Actually I tried this already and came up with a string of powers of k > another string of powers of k. Still can't prove anything.
Solving a polynomial inequality doesn't require much more than finding the roots of the polynomial.

This is a good use of a computer algebra system to just approximate the roots -- you don't need to know what they are exactly, just that they are negative!

If you've really studied polynomials in depth, you might also know a trick to count the number of positive roots without actually having to find them.



Anyways, I mentioned that approach because I know it will work and it's very straightforward, even if it turns out to be tedious.



As for calculus, working with inequalities is one of the great applications. :smile: Differential approximation (or more generally, Taylor series with remainder) is one of the great tools for the mathematician. You will lose some accuracy in the inequality -- but that's fine in this problem, as long as you bound the errors so you can make rigorous statements. (And don't waste so much accuracy that you can no longer prove what you want to prove)
 
  • #7
P.S. when you want to square an inequality, you should take care to split things into the relevant cases, because each one requires different treatment: both sides positive, both sides negative, and one positive/one negative.
 
  • #8
I think I have come up with a reasonable solution:

Continuing from my last equation, which is: [tex](k+1)\sqrt{k} + \sqrt{k+2} > (k+1)\sqrt{k+1}[/tex]

I rearrange it to form: [tex]0 > (k+1)\sqrt{k+1} - (k+1)\sqrt{k} - \sqrt{k+2}[/tex]

which is: [tex](k+1)\sqrt{k+1} - (k+1)\sqrt{k} - \sqrt{k+2} < 0[/tex]

or: [tex](k+1)(\sqrt{k+1} - \sqrt{k}) - \sqrt{k + 2} \ < \ 0[/tex] ... (4)

I took the LHS of the inequality (4) and used a http://xrjunque.nom.es/precis/Polycalc.aspx" [Broken] to create a graph of the function.

Here's the graph I got (X-axis = k value; Y-axis = value of LHS):
http://www.fileden.com/files/2006/12/20/534119/Math-As1-Graph.png [Broken]

The graph is a smooth curve and its values are always on the negative side of the Y-axis. (Note that we are interested in k>=1 only.) Since the function is a polynomial function, it is safe to assume that its graph is a smooth curve infinitely decreasing along the Y-axis as the value of k increases along the X-axis. Therefore the LHS is always < 0, and the proposition is proved.

Is this reasonable? :uhh:
 
Last edited by a moderator:
  • #9
agent007bond said:
Is this reasonable? :uhh:
That's a hard question to answer.

On one end of the scale, if someone's life depended on getting the answer right, I would want more rigor than this graph! On the other end of the scale, if this was just a minor conjecture in a bigger problem I'm working through, I probably wouldn't give it any more thought than that plot. (Although I might have used larger bounds)

Another angle is that the intent of a homework problem is not to get the answer to the problem, but to demonstrate some area of knowledge. If your professor was looking for a demonstration of working with approximations and differential approximations and what-not, he may not be satisfied with a plot.


Anyways, the next graphical level of rigor up is if you can estimate what that asymptote is supposed to be. If you knew that, for example, the plot was supposed to converge to a line of slope -1, then you should be a lot more confident in the graph than if, for example, the graph was supposed to be asymptotically horizontal.


One graphical feature is that it seems to be decreasing. If you can prove that, you would have a perfectly rigorous proof. :smile: But that might be just as hard as the original inequality.




For the record, if I had to solve this in the real world, I would have asked Mathematica to solve the equality to make sure there were no positive zeroes, and then plugged in a number to check if the graph was in the first or the fourth quadrant.

If I didn't have mathematica, I would try some combination of asymptotics and differential approximations.
 
  • #10
That's a lot to process. Estimating asymptotes is something I am not so confident about. I will give it a try. But I do agree that the professor wants us to use inductive reasoning to solve the problem, so resorting to graphical analysis may not satisfy him. However, this professor who taught us inductive reasoning in university is quite young and he is found to make mistakes easily. I suspect he prepared the assignment questions without verifying their feasability.

PS: I plotted the graph to 1 million (X-axis), and it looks very similar.
 
  • #11
This is a solution that my friend has suggested. Basically it does a lot of induction to come up with the proof! (Isn't that what mathematical induction is all about?)

I will continue from equation (3) in my original message, which is: [tex]\sum_{i=1}^{k+1} \frac{\sqrt{i+1}}{2i} > \frac{\sqrt{k}}{2} + \frac{\sqrt{k+2}}{2k+2}[/tex]

The goal is to achieve the RHS of equation (2), where (2) is: [tex]\sum_{i=1}^{k+1} \frac{\sqrt{i+1}}{2i} > \frac{\sqrt{k+1}}{2}[/tex]

Taking the RHS of (3), we have:
[tex]\frac{\sqrt{k}}{2} + \frac{\sqrt{k+2}}{2(k+1)}[/tex] [note that [tex]2k+2 = 2(k+1)[/tex]]

[tex]= \frac{\sqrt{k}(k+1) + \sqrt{k+2}}{2(k+1)}[/tex]

[tex]> \frac{\sqrt{k}(k+1) + \sqrt{k+1}}{2(k+1)}[/tex] [[tex]\because \sqrt{k+2} > \sqrt{k+1}[/tex], and all other terms are positive]

[tex]= \frac{\sqrt{k}\sqrt{k+1}^2 + \sqrt{k+1}}{2(k+1)}[/tex] [[tex]\because (k+1) = \sqrt{k+1}^2[/tex]]

[tex]= \frac{\sqrt{k+1}(\sqrt{k}\sqrt{k+1} + 1)}{2(k+1)}[/tex] [taking common factor [tex]\sqrt{k+1}[/tex] out]

[tex]> \frac{\sqrt{k+1}(\sqrt{k}\sqrt{k} + 1)}{2(k+1)}[/tex] [[tex]\because \sqrt{k+1} > \sqrt{k}[/tex], and all other terms are positive]

[tex]= \frac{\sqrt{k+1}(k + 1)}{2(k+1)}[/tex]

[tex]= \frac{\sqrt{k+1}}{2}[/tex]

From the above, we see that,
[tex]\sum_{i=1}^{k+1} \frac{\sqrt{i+1}}{2i} > \frac{\sqrt{k}(k+1) + \sqrt{k+2}}{2(k+1)} > \frac{\sqrt{k+1}(\sqrt{k}\sqrt{k+1} + 1)}{2(k+1)} > \frac{\sqrt{k+1}}{2}[/tex]

By the transitive property of inequalities, we have:
[tex]\sum_{i=1}^{k+1} \frac{\sqrt{i+1}}{2i} > \frac{\sqrt{k+1}}{2}[/tex]

Therefore the proposition is proved.
The disadvantage of the above solution is that one has to come up with (induce) the right inequalities to substitute in, (such as [tex]\sqrt{k+1} > \sqrt{k}[/tex]) so that one can induce the final goal from the initial function. This may require a lot of trial and error and facing of difficulties, and there is no guarantee that one can find the right inequalities to prove or disprove the proposition.

Anyway I am including both the graphical method and the inductive method (above) in my assignment report. :smile:
 

What is mathematical induction?

Mathematical induction is a method used to prove mathematical statements that follow a specific pattern or sequence. It involves proving that the statement is true for a base case, usually the first number in the sequence, and then proving that if the statement is true for a specific number, it must also be true for the next number in the sequence.

How does mathematical induction prove inequality?

In order to prove an inequality using mathematical induction, we first need to establish the base case, usually the smallest value of the sequence. Then, we assume that the inequality is true for a specific value of the sequence, and use this assumption to prove that it is also true for the next value in the sequence. This process is repeated until we can prove that the inequality holds for all values in the sequence, thereby proving the inequality.

Can mathematical induction be used to prove all inequalities?

No, mathematical induction can only be used to prove inequalities that follow a specific pattern or sequence. It is not a method that can be applied to all types of inequalities.

What are the key elements of a mathematical induction proof?

The key elements of a mathematical induction proof are the base case, the induction hypothesis, and the inductive step. The base case establishes the truth of the statement for the first value in the sequence. The induction hypothesis assumes the truth of the statement for a specific value in the sequence. The inductive step uses the induction hypothesis to prove the truth of the statement for the next value in the sequence.

Are there any limitations to using mathematical induction?

Yes, mathematical induction can only be used to prove statements that follow a specific pattern or sequence. It also requires careful reasoning and logical thinking, which can be challenging for some individuals. Additionally, in some cases, alternative methods may be more efficient or appropriate for proving inequalities.

Similar threads

  • Calculus and Beyond Homework Help
Replies
2
Views
664
  • Calculus and Beyond Homework Help
Replies
3
Views
444
  • Calculus and Beyond Homework Help
Replies
15
Views
1K
  • Calculus and Beyond Homework Help
Replies
17
Views
1K
  • Calculus and Beyond Homework Help
Replies
1
Views
252
  • Calculus and Beyond Homework Help
Replies
9
Views
865
  • Calculus and Beyond Homework Help
Replies
5
Views
220
  • Calculus and Beyond Homework Help
Replies
16
Views
1K
  • Calculus and Beyond Homework Help
Replies
29
Views
1K
Replies
12
Views
267
Back
Top