Proof by Induction - Inequality

[ksm100]

Homework Statement

show by induction that ((1/2)*(3/4)*(5/6)*...*(2n-1)/(2n))^2 is less than/equal to (1/(3n+1)) for n=1, 2, ...

The Attempt at a Solution

For n=1, (1/2)^2 less than/equal to 1/4 is true (1/4=1/4), so the statement holds for n=1.

Assume the statement is true for n, i.e.,
((1/2))*(3/4)*(5/6)*...*(2n-1)/(2n))^2 is less than/equal to (1/(3n+1)).

Now show true for n+1, i.e.
((1/2))*(3/4)*(5/6)*...*(2n-1)/(2n)*(2n+1)/(2n+2))^2 less than/equal to (1/(3n+4)).

By induction hypothesis,
[((1/2))*(3/4)*(5/6)*...*(2n-1)/(2n))^2]*((2n+1)/(2n+2))^2 less than/equal to (1/(3n+1))*((2n+1)/(2n+2))^2.

So then I tried to prove this by expanding the right side to get:
(4n^2+4n+1)/(12n^3+28n^2+20n+4), and then to show that this expression is less than (1/(3n+4)) but it didn't seem to be working out, and was getting a bit complicated so I thought that probably wasn't the right thing to be doing..

If anyone could provide some advice that would be greatly appreciated. Thanks!

 

[Galadirith]

Hi ksm100,

Well this was interesting I wasn't sure where to go from where you left off, I just learned about induction in my A-levels last year. I think everything you have done up to that point is perfect. So as you said, if we can show that:

$$\left(\frac{1}{3n+1}\right)\left(\frac{2(n+1)-1}{2(n+1)}\right)^2 \ \leq \ \frac{1}{3(n+1)+1} \ \ \ (i)$$

(well call this equation (i) so I can refer to it later), is true then the inequality you formed from the induction hypothesis must also be true, and as you have already shown a trivial case is true, by induction the original inequality must also be true for all n.

Now Ill rewrite that slightly differently, instead of expanding the 2(n+1) term as 2n+2 ill keep the 2 outside, there's no real necessity to do that you'll hopefully see that even if I didn't keep 2 as a factor, you could still follow this proof. So ill rewrite it as:

$$\frac{(2n+1)^2}{4(3n+1)(n+1)^2} \ \leq \ \frac{1}{3n+4}$$

and expanding the LHS:

$$\left(\frac{1}{4}\right)\left(\frac{4n^2 + 4n + 1}{3n^3 + 7n^2 + 5n + 1}\right) \ \leq \ \frac{1}{3n+4}$$

Now as n > 0, I know that 3n + 4 will also be > 1. That may or may not be necessary to state. I suppose its kind of obvious but as dealing with an inequality probably best to state. So from that I multiply both sides by 3n + 4, and also I will multiply both sides by 4 to get rid of the fraction 1/4 on the left:

$$\frac{(3n+4)(4n^2 + 4n + 1)}{3n^3 + 7n^2 + 5n + 1} \ \leq \ 4$$

and then this can be expanded to:

$$\frac{12n^3 + 28n^2 + 19n + 4}{3n^3 + 7n^2 + 5n + 1} \ \leq \ 4$$

Now were dealing with a "top heavy" polynomial fraction here, so the course of action here would be to perform polynomial Long Division, so let's do it:

$$\begin{array}{r@{}rrrr} & 4 \\ \cline {2-5} 3n^3 + 7n^2 + 5n +1 \; | & 12n^3 & + 28n^2 & + 19n & 4 \\ & 12n^3 & + 28n^2 & + 20n & 4 \\ \cline{2-5} & 0 & + 0 & - n & + 0 \\$$

From this we can see that:

$$\frac{12n^3 + 28n^2 + 19n + 4}{3n^3 + 7n^2 + 5n + 1} \ = \ 4 \ - \ \frac{n}{3n^3 + 7n^2 + 5n + 1} \ = \ 4 \ - \ \frac{n}{(3n+1)(n+1)^2}$$

so we can say:

$$4 \ - \ \frac{n}{(3n+1)(n+1)^2}} \ \leq \ 4$$

rearranged we get:

$$0 \ \leq \ \frac{n}{(3n+1)(n+1)^2}}$$

and as should be evident, the RHS has to be greater than 0, which implies that inequality (i) is also true :D. I believe that this paired with the work that you have already done should constitute a sufficient proof, I think you certainly need to make sure all the wording etc is correct, I certainly haven't put it in a "Proof" format. Have fun ksm100 :D

 

[ksm100]

Thank you for your help Galadirith..
I can follow everything that you've done to come up with the last expression that you gave, but then I don't see how that implies that (i) is true.. maybe there's something obvious I'm just not seeing..?
Again, thanks for your reply

 

[Galadirith]

Hey ksm100, that's no problem.

Rite well I believe I can see why your not completely happy with it. So all I have done is rearrange (i), so because of that if I can prove that the final inequality I presented is true, then any rearrangement of that inequality must also be true.

However, Ill propose another way of working this question, which should be more clear. so well start with (i) again:

$$\left(\frac{1}{3n+1}\right)\left(\frac{2(n+1)-1}{2(n+1)}\right)^2 \ \leq \ \frac{1}{3(n+1)+1} \ \ \ (i)$$

which can be written as (without factoring the 4 in the denominator):

$$\frac{4n^2 + 4n + 1}{12n^3 + 28n^2 + 20n + 4} \ \leq \ \frac{1}{3n+4}$$

Now for the LHS, let's multiply the numerator and denominator by 3n+4:

$$\frac{(3n + 4)(4n^2 + 4n + 1)}{(3n + 4)(12n^3 + 28n^2 + 20n + 4)} \ \leq \ \frac{1}{3n+4}$$

expanding the top:

$$\frac{12n^3 + 28n^2 + 19n + 4}{(3n + 4)(12n^3 + 28n^2 + 20n + 4)} \ \leq \ \frac{1}{3n+4}$$

Now notice that the numerator is almost the same as a factor in the denominator, and if we add this expression to the numerator (+n - n), then we get this:

$$\frac{12n^3 + 28n^2 + 19n + 4 + n - n}{(3n + 4)(12n^3 + 28n^2 + 20n + 4)} \ \leq \ \frac{1}{3n+4}$$

$$\frac{12n^3 + 28n^2 + 20n + 4 - n}{(3n + 4)(12n^3 + 28n^2 + 20n + 4)} \ \leq \ \frac{1}{3n+4}$$

now we haven't changed the value of the numerator in any way as n - n = 0, but we can now do this:

$$\frac{(12n^3 + 28n^2 + 20n + 4) - n}{(3n + 4)(12n^3 + 28n^2 + 20n + 4)} \ \leq \ \frac{1}{3n+4}$$

$$\frac{12n^3 + 28n^2 + 20n + 4}{(3n + 4)(12n^3 + 28n^2 + 20n + 4)} \ - \ \frac{n}{(3n + 4)(12n^3 + 28n^2 + 20n + 4)} \ \leq \ \frac{1}{3n+4}$$

dividing through the common factors of the first fraction (and factoring the second fraction expression to make it look nicer :D):

$$\frac{1}{(3n + 4)} \ - \ \frac{n}{4(3n + 4)(3n+1)(n+1)^2} \ \leq \ \frac{1}{3n+4} \ \ \ (ii)$$

Now it should be evident that:

$$\frac{n}{4(3n + 4)(3n+1)(n+1)^2} > 0$$

for all positive values of n, or the set of natural numbers as you originally stated. If its not then there are many ways you could prove the expression is indeed greater than 0, you could consider where the roots of the expression lie, and asymptotes and then consider the value of the function at higher values of n, or through some simple calculus, but I won't go into that here.

So that implies that the LHS of (ii) must be less than the RHS, which does show that (i) is indeed true, as:

$$\frac{1}{(3n + 4)} \ - \ \frac{n}{4(3n + 4)(3n+1)(n+1)^2} = \left(\frac{1}{3n+1}\right)\left(\frac{2(n+1)-1}{2(n+1)}\right)^2$$

which is what we actually did through out. It might in fact be much better to show that those two are equal, and then use that as a substitution for the LHS of (i). Now for future thought what was the general technique employed here.

well consider the inequality:

$$A(n) \ \leq \ B(n)$$

where A(n) and B(n) are some functions of n. We then attempt to put the the LHS into a form:

$$A(n) = B(n) - C(n)$$

where C(n) is also a function of n such that every value of C(n) for our domain of n is greater than 0, so we have:

$$B(n) - C(n) \ \leq \ B(n)$$

Which we can see due to the properties of C(n), that by inspection this inequality is indeed true.

Hopefully that all makes more sense to you now ksm100, have fun :D