Prove Inequality by Mathematical Induction

[agent007bond]

I have to prove the following via mathematical induction, \(\displaystyle \forall n \in Z^+\)

\(\displaystyle \sum_{i=1}^n \frac{\sqrt{i+1}}{2i} > \frac{\sqrt{n}}{2}\)

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

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

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

Comparing with equation (1) I can write the following: \(\displaystyle \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, \(\displaystyle \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: \(\displaystyle \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: \(\displaystyle \frac{\sqrt{k}}{2} + \frac{\sqrt{k+2}}{2k+2} > \frac{\sqrt{k+1}}{2}\)

Simplifying it, I can come up with: \(\displaystyle (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?!

 

[mmm4444bot]

Since each term in the original summation contains a factor of 1/2, we can factor it out. Therefore, the given inequality simplifies by multiplying both sides by 2.

\(\displaystyle \frac{1}{2} \cdot \sum_{i=1}^n \frac{\sqrt{i + 1}}{i} \ > \ \frac{\sqrt{n}}{2}\)

\(\displaystyle \sum_{i=1}^n \sqrt{i + 1} \ > \ \sqrt{n}\)

I worked the proof separately, and I reached a point that agrees with your result below, except for the previously-removed factors of 1/2 and the direction of the inequality sign.

?

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

My result, up to that point, is:

\(\displaystyle \sqrt{k + 1} \ - \ \frac{\sqrt{k + 2}}{k + 1} > \sqrt{k}\)

which is the same as:

\(\displaystyle \sqrt{k} \ + \ \frac{\sqrt{k + 2}}{k + 1} \ < \ \sqrt{k + 1}\)

I made no attempt to verify your lecturer's statement (although, I did use the Transitive Property of Inequalities to write my result, so I suspect that I used the same route). I also did not try to figure out why the inequality is reversed in your result.)

Here's how I proceeded.

\(\displaystyle \sqrt{k + 1} \ (k + 1) \ - \ \sqrt{k + 2} \ > \ \sqrt{k} \ \sqrt{k + 1}\)

\(\displaystyle \sqrt{k + 1} \ (k + 1) \ - \ \sqrt{k} \ \sqrt{k + 1} \ > \ \sqrt{k + 2}\)

\(\displaystyle \sqrt{k + 1} \ (k + 1 - \sqrt{k}) \ > \ \sqrt{k + 1}\)

\(\displaystyle k + 1 - \sqrt{k} \ > \ 1\)

\(\displaystyle k \ > \ \sqrt{k}\)

Seems to work; however, "trust, but verify".

 

[agent007bond]

Thank you for your detailed reply.
However, I think you have made mistakes, or I am making mistakes. Here are the steps:
\(\displaystyle \sum_{i=1}^n \frac{\sqrt{i + 1}}{i} \ > \ \sqrt{n}\) (I think you missed the \(\displaystyle ``\frac{}{i}"\) in your message!)

When n = k, \(\displaystyle \ \sum_{i=1}^k \frac{\sqrt{i + 1}}{i} \ > \ \sqrt{k}\) (this is assumed to be true)

When n=k+1, \(\displaystyle \ \sum_{i=1}^{k+1} \frac{\sqrt{i + 1}}{i} \ > \ \sqrt{k+1}\)

\(\displaystyle \sum_{i=1}^k \frac{\sqrt{i + 1}}{i} + \frac{\sqrt{k + 2}}{k+1} \ > \ \sqrt{k+1}\)

Applying Transitive Property of Inequalities,
\(\displaystyle \sqrt{k} + \frac{\sqrt{k + 2}}{k+1} \ > \ \sqrt{k+1} \\) (you are getting < instead of >.. why?)

Following what you did, I rearrange:
\(\displaystyle \sqrt{k} \ > \ \sqrt{k+1} - \frac{\sqrt{k + 2}}{k+1}\)

\(\displaystyle \sqrt{k+1} - \frac{\sqrt{k + 2}}{k+1} \ < \ \sqrt{k}\) ... (4)
But this following step in your message seems wrong.

My result, up to that point, is:
\(\displaystyle \sqrt{k + 1} \ - \ \frac{\sqrt{k + 2}}{k + 1} > \sqrt{k}\)
...
Here's how I proceeded.
\(\displaystyle \sqrt{k + 1} \ (k + 1) \ - \ \sqrt{k + 2} \ > \ \sqrt{k} \ \sqrt{k + 1}\)
\(\displaystyle \sqrt{k + 1} \ (k + 1) \ - \ \sqrt{k} \ \sqrt{k + 1} \ > \ \sqrt{k + 2}\)
\(\displaystyle \sqrt{k + 1} \ (k + 1 - \sqrt{k}) \ > \ \sqrt{k + 1}\)

Shouldn't it be the following (the step after "Here's how I proceeded.")?: \(\displaystyle \sqrt{k + 1} \ (k + 1) \ - \ \sqrt{k + 2} \ > \ \sqrt{k}(k + 1)\)
Also, for the last two steps quoted above, you changed the \(\displaystyle \sqrt{k + 2}\) to \(\displaystyle \sqrt{k + 1}\) without any apparent reason!

By following the same method as you did, I proceed from (4):
\(\displaystyle \frac{\sqrt{k+1}(k+1) - \sqrt{k + 2}}{k+1} \ < \ \sqrt{k}\)

\(\displaystyle \sqrt{k+1}(k+1) - \sqrt{k + 2} \ < \ \sqrt{k}(k+1)\)

Now I don't know how to proceed...

 

[agent007bond]

This is the only reasonable way that I could prove the inequality:

I rearranged the last line \(\displaystyle \sqrt{k+1}(k+1) - \sqrt{k + 2} \ < \ \sqrt{k}(k+1)\)

to this: \(\displaystyle \sqrt{k+1}(k+1) - \sqrt{k + 2} - \sqrt{k}(k+1) \ < \ 0\)

then to this: \(\displaystyle (k+1)(\sqrt{k+1} - \sqrt{k}) - \sqrt{k + 2} \ < \ 0\)

I took the LHS of the inequality and used this free Polynomial Calculator to create a graph of the function:
http://xrjunque.nom.es/precis/Polycalc.aspx [sorry, URL is off, so I can't link to it].

Here's the graph I got (X-axis = k value; Y-axis = value of LHS):

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.

Reasonable? :?

 

[mmm4444bot]

\(\displaystyle \sum_{i=1}^n \frac{\sqrt{i + 1}}{i} \ > \ \sqrt{n}\) (I think you missed the \(\displaystyle ``\frac{}{i}"\) in your message!)

Yup, I sure did. That's a typographical error.

Applying Transitive Property of Inequalities,
\(\displaystyle \sqrt{k} + \frac{\sqrt{k + 2}}{k+1} \ > \ \sqrt{k+1} \\) (you are getting < instead of >.. why?)

Oops, I shredded my scratch paper from last night! I can't remember what I did, except that I brought three different workings together. (Apparently, too many, for me, heh, heh.)

\(\displaystyle \sqrt{k+1}(k+1) - \sqrt{k + 2} \ < \ \sqrt{k}(k+1)\)

Okay, I started from scratch, and I agree with your result.

Now I don't know how to proceed Hmmm, off the top of my head, neither do I. I will play with it more, after dinner sometime.

I apologize for creating needless work, for you, correcting all of my errors.

 

[mmm4444bot]

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.

Reasonable? Yes, I think so.

However, inductive proofs generally end with an algebraic manipulation that results in an obviously-true statement.

Resorting to a graphical proof is something that we could have done much sooner. (I'm not sure what motivated this exercise. If the motivation is both inductive reasoning and graphical analysis, then hey, you're done.)

I'm not satisified, yet! (But, maybe I'll resign myself to be satisfied, later tonight. )

 

[agent007bond]

Well, graphical analysis is not disallowed, but the motivation is to prove by inductive reasoning.

I will wait for your answer tonight.
My assignment submission is tomorrow 25 Feb 2010, at 12:30 pm (UTC+0800).
The time of this post is 24 Feb 2010, 9:55 am (UTC+0800). (Hint: Check the post time shown in your computer.)

PS: The graph looks very similar even when I extend the X-axis to 1 million.

 

[mmm4444bot]

I goofed around with it some more this morning, but I gave up.

At one point, I tried to fool myself, again.

(heh, heh)

I went back to the original inequality, and focused on how much each side increased with each increment of n.

If the increase on the LHS can be shown to always be greater than the RHS, then that would prove the original inequality, yes?

But that pretty much boiled down to the same squirrely situation with radicals.

Okay, I'm satisfied that I cannot find a form where the solution is apparent.

Maybe someone else will comment; otherwise, I think you're good to go with your inductive set-up and graphical finish. Please let us know how it all turns out.

Cheers ~ Mark

 

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

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

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

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

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

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

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

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

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

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

From the above, we see that,
\(\displaystyle \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}\)

By the transitive property of inequalities, we have:
\(\displaystyle \sum_{i=1}^{k+1} \frac{\sqrt{i+1}}{2i} > \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 \(\displaystyle \sqrt{k+1} > \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.

PS: I attempted the same method after factoring the \(\displaystyle \frac{1}{2}\) out as you have done in your first message. It works after the removal too.