Results 1 to 5 of 5

Math Help - Need help using induction and inequalites

  1. #1
    Newbie
    Joined
    Feb 2010
    Posts
    19

    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.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    Quote Originally Posted by Enkie View Post
    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
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Feb 2010
    Posts
    19
    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.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    Quote Originally Posted by Enkie View Post
    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)
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Feb 2010
    Posts
    19
    Wow. Tricky problems with simple elegant solutions. Thank you very much.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Strong induction vs. structural induction?
    Posted in the Discrete Math Forum
    Replies: 13
    Last Post: April 21st 2011, 12:36 AM
  2. Replies: 10
    Last Post: June 29th 2010, 12:10 PM
  3. Quadratic Inequalites
    Posted in the Algebra Forum
    Replies: 8
    Last Post: May 23rd 2010, 10:58 AM
  4. Induction
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: May 8th 2010, 08:31 AM
  5. Mathemtical Induction Proof (Stuck on induction)
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: March 8th 2009, 09:33 PM

Search Tags


/mathhelpforum @mathhelpforum