Results 1 to 4 of 4

Math Help - Proving an inequality without induction.

  1. #1
    Newbie
    Joined
    Nov 2013
    From
    Cardiff - Wales
    Posts
    5

    Proving an inequality without induction.

    Hi guys, I have to complete this question but I have no idea how to solve it, not even an inkling.

    The question is
    For each integer that n is greater than or equal to 1, prove (without induction) that:


    (2^2n / 2n) is less than or equal to the set (2n )(n) which is less than 2^2n


    (See attached thumbnail for much clearer version of question)

    Thanks in advance for your help! (I hope)

    Andrew
    Attached Thumbnails Attached Thumbnails Proving an inequality without induction.-screen-shot-2013-11-04-03.55.41.png  
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Member
    Joined
    Jun 2012
    From
    Georgia
    Posts
    176
    Thanks
    22

    Re: Proving an inequality without induction.

    For the purpose of this post, let f(n) = the left expression, g(n) = the center expression, and h(n) = the right expression.

    It is clear that f(n) < h(n), so it's all about establishing where g(n) lies.

    Maybe you should turn this into an initial-value problem. Specifically, show that f'(n) <= g'(n) < h'(n), and f(1) <= g(1) < h(1). Of course, g'(n) is really gonna get messy, so maybe this isn't the way to go. But remember, you don't necessarily have to solve for g'(n); you just have to show that it lies between f'(n) and h'(n).
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member
    Joined
    Jul 2012
    From
    INDIA
    Posts
    826
    Thanks
    209

    Re: Proving an inequality without induction.

    You may try the attached approach. Proving an inequality without induction.-04-nov-13.png
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Nov 2010
    Posts
    1,765
    Thanks
    683

    Re: Proving an inequality without induction.

    You know that 2^{2n} is the number of elements in the power set of a 2n-element set and \binom{2n}{n} is the number of ways to choose n elements from a set of 2n elements (the set of n-combinations is a proper subset of the power set since the power set contains the empty set while the set of n-combinations does not).

    Now, you know that \sum_{i=0}^{2n}\binom{2n}{i} = 2^{2n}. Also, \binom{2n}{n} \ge \binom{2n}{i} for all i \in \mathbb{Z}, and \binom{2n}{n} = \binom{2n}{i} only if i = n. Since 2n\ge 2, you know that \binom{2n}{n} \ge \binom{2}{1} = 2 = \binom{2n}{0}+\binom{2n}{2n}. Rewriting the identity:

    \begin{align*}2^{2n} & = \sum_{i=0}^{2n}\binom{2n}{i} \\ & = \binom{2n}{0} + \binom{2n}{2n} + 2\sum_{i=1}^{n-1}\binom{2n}{i} + \binom{2n}{n} \\ & \le \binom{2n}{n} + 2\sum_{i=1}^{n-1}\binom{2n}{n} + \binom{2n}{n} \\ & = 2n\binom{2n}{n}\end{align*}

    From here, divide both sides by 2n, and you get the final inequality.
    Last edited by SlipEternal; November 4th 2013 at 06:53 AM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Proving an inequality without induction
    Posted in the Algebra Forum
    Replies: 1
    Last Post: November 3rd 2013, 07:01 PM
  2. Proving an inequality without induction
    Posted in the Discrete Math Forum
    Replies: 7
    Last Post: June 30th 2013, 03:17 PM
  3. Proving inequality through induction
    Posted in the Advanced Math Topics Forum
    Replies: 18
    Last Post: May 22nd 2012, 09:13 AM
  4. Replies: 3
    Last Post: December 12th 2010, 01:16 PM
  5. induction inequality
    Posted in the Algebra Forum
    Replies: 1
    Last Post: October 26th 2008, 08:46 AM

Search Tags


/mathhelpforum @mathhelpforum