# Thread: Need help using induction and inequalites

1. ## Need help using induction and inequalites

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.

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

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

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

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