Prove Inequality by Mathematical Induction

[agent007bond]

Homework Statement

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

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: \sum_{i=1}^k \frac{\sqrt{i+1}}{2i} > \frac{\sqrt{k}}{2} ... (1)

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

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

Comparing with equation (1) I can write the following: \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}

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

According to our lecturer, from (2) and (3) we have: \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}

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

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

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?!

 

[Hurkyl]

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)

 

[agent007bond]

I guess so. For \frac{\sqrt{k}}{2} + \frac{\sqrt{k+2}}{2k+2} > \frac{\sqrt{k+1}}{2}, 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?)

 

[Hurkyl]

Well, if square roots are the problem... don't you know how to get rid of them?

 

[agent007bond]

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?

 

[Hurkyl]

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

 

[Hurkyl]

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.

 

[agent007bond]

I think I have come up with a reasonable solution:

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

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

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

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

I took the LHS of the inequality (4) and used a http://xrjunque.nom.es/precis/Polycalc.aspx" 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

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?

 

[Hurkyl]

Is this reasonable?

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

 

[agent007bond]

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.

 

[agent007bond]

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: \sum_{i=1}^{k+1} \frac{\sqrt{i+1}}{2i} &gt; \frac{\sqrt{k}}{2} + \frac{\sqrt{k+2}}{2k+2}

The goal is to achieve the RHS of equation (2), where (2) is: \sum_{i=1}^{k+1} \frac{\sqrt{i+1}}{2i} &gt; \frac{\sqrt{k+1}}{2}

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

= \frac{\sqrt{k}(k+1) + \sqrt{k+2}}{2(k+1)}

&gt; \frac{\sqrt{k}(k+1) + \sqrt{k+1}}{2(k+1)} [\because \sqrt{k+2} &gt; \sqrt{k+1}, and all other terms are positive]

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

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

&gt; \frac{\sqrt{k+1}(\sqrt{k}\sqrt{k} + 1)}{2(k+1)} [\because \sqrt{k+1} &gt; \sqrt{k}, and all other terms are positive]

= \frac{\sqrt{k+1}(k + 1)}{2(k+1)}

= \frac{\sqrt{k+1}}{2}

From the above, we see that,
\sum_{i=1}^{k+1} \frac{\sqrt{i+1}}{2i} &gt; \frac{\sqrt{k}(k+1) + \sqrt{k+2}}{2(k+1)} &gt; \frac{\sqrt{k+1}(\sqrt{k}\sqrt{k+1} + 1)}{2(k+1)} &gt; \frac{\sqrt{k+1}}{2}

By the transitive property of inequalities, we have:
\sum_{i=1}^{k+1} \frac{\sqrt{i+1}}{2i} &gt; \frac{\sqrt{k+1}}{2}

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 \sqrt{k+1} &gt; \sqrt{k}) 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.