Need help using induction and inequalites

**Enkie** · February 10th 2010, 07:18 PM

I am taking a discrete math class right now and am having some difficulties with induction when working with inequalities. My teacher is very strict about proofs, rightly so, and knocks points off brutally for mistakes

I can show that its true for n = 1 where both sides are equal to 1/2. The gap between the two widens though when n = 2. Then I plug in k in place of n and assume it to be an arbitrary element of the set of natural positive numbers. Now looking at the sequence it looks like a factorial of odds on top and a factorial of evens on the bottom which is greater or equal to 1/2k. I am not sure what good the factorial would do for this problem and I am not even sure if its relevant.

So it would seem that this would be true already because 1/2k will get smaller as k approaches infinity vs the sequence which gets smaller more slowly. I then increment the k to k+1. I then tried to do what I would normally do with the type of induction problems we have been doing so far, which is take the closed form of the sequence with k inside and add it to the k+1th iteration and try to prove that adding those together is equivalent to the k+1th closed form.

I tried doing that in this case and multiplied 1/2k times the k+1th iteration of the sequence and after a little bit of factoring got the other side of the inequality at k+1 and then a small fraction. I am somewhat sure that what I have done is wrong.

Any assistance would be greatly appreciated.

**Drexel28** · February 10th 2010, 08:01 PM

Originally Posted by Enkie

I am taking a discrete math class right now and am having some difficulties with induction when working with inequalities. My teacher is very strict about proofs, rightly so, and knocks points off brutally for mistakes

I can show that its true for n = 1 where both sides are equal to 1/2. The gap between the two widens though when n = 2. Then I plug in k in place of n and assume it to be an arbitrary element of the set of natural positive numbers. Now looking at the sequence it looks like a factorial of odds on top and a factorial of evens on the bottom which is greater or equal to 1/2k. I am not sure what good the factorial would do for this problem and I am not even sure if its relevant.

So it would seem that this would be true already because 1/2k will get smaller as k approaches infinity vs the sequence which gets smaller more slowly. I then increment the k to k+1. I then tried to do what I would normally do with the type of induction problems we have been doing so far, which is take the closed form of the sequence with k inside and add it to the k+1th iteration and try to prove that adding those together is equivalent to the k+1th closed form.

I tried doing that in this case and multiplied 1/2k times the k+1th iteration of the sequence and after a little bit of factoring got the other side of the inequality at k+1 and then a small fraction. I am somewhat sure that what I have done is wrong.

Any assistance would be greatly appreciated.

Notice this is equivalent to proving that $0\leqslant 1\cdot 3\cdots(2n-1)-2\cdots(2n-2)$ . So, let us call $\ell_n=1\cdots (2n-1)-2\cdots(2n-2)$ . Then, $\ell_1=1-0\geqslant 0$ . So, now assume that $\ell_n\geqslant 0$ then $\ell_{n+1}=1\cdots(2n-1)\cdot(2n+1)-2\cdots(2n-2)\cdots(2n)$ . Now clearly $2n+1\geqslant 2n$ and so

$1\cdots(2n-1)\cdot(2n+1)-2\cdots(2n-1)\cdot 2n$ $\geqslant 1\cdots(2n-1)\cdot 2n-2\cdots (2n-2)\cdot 2n=2n\cdot \ell_n\geqslant 2n\cdot 0=0$ . The conclusion follows

**Enkie** · February 10th 2010, 08:18 PM

Thanks. I will have to spend some time working through this proof so that I understand it well enough to write it the way the teacher will want. I appreciate the help. I am somewhat confused by the first step. I probably need to just stare it at longer.

**Drexel28** · February 10th 2010, 08:23 PM

Originally Posted by Enkie

Thanks. I will have to spend some time working through this proof so that I understand it well enough to write it the way the teacher will want. I appreciate the help. I am somewhat confused by the first step. I probably need to just stare it at longer.

$\frac{1}{2n}\leqslant\frac{1\cdots(2n-1)}{2\cdots 2n}\implies 1\leqslant 2n\cdot\frac{1\cdots(2n-1)}{2\cdots 2n}=\frac{1\cdots (2n-1(}{2\cdots(2n-2)}$ $\implies 2\cdots (2n-1)\leqslant 1\cdots(2n-1)\implies 0\leqslant 1\cdots (2n-1)-2\cdots(2n-2)$

**Enkie** · February 10th 2010, 08:26 PM

Wow. Tricky problems with simple elegant solutions. Thank you very much.

Thread: Need help using induction and inequalites

LinkBack

Thread Tools

Display

Need help using induction and inequalites

Similar Math Help Forum Discussions

Strong induction vs. structural induction?

Rigorously prove the principle of complete induction from mathematical induction??

Quadratic Inequalites

Induction

Mathemtical Induction Proof (Stuck on induction)

Search Tags