Results 1 to 4 of 4

Math Help - combinatorial inequality

  1. #1
    Junior Member
    Joined
    Jun 2007
    Posts
    63

    combinatorial inequality

    Hi. I am trying to prove the following:

    1 + C(2n, 1) + C(2n, 2) + ... + C(2n, k) <= (2n)^k for n >= k > 1.

    I would appreciate any suggestions you all may have.

    Thanks.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Dec 2009
    Posts
    3,120
    Thanks
    1
    Quote Originally Posted by kkoutsothodoros View Post
    Hi. I am trying to prove the following:

    1 + C(2n, 1) + C(2n, 2) + ... + C(2n, k) <= (2n)^k for n >= k > 1.

    I would appreciate any suggestions you all may have.

    Thanks.
    You could prove it via Proof By Induction...

    P(k)

    \displaystyle\ 1+\binom{2n}{1}+\binom{2n}{2}+....+\binom{2n}{k}\ \le\ (2n)^k\ ?

    P(k+1)

    \displaystyle\ 1+\binom{2n}{1}+\binom{2n}{2}+....+\binom{2n}{k}+\  binom{2n}{k+1}\ \le\ (2n)^{k+1}\ ?

    Try to prove that P(k+1) will be valid if P(k) is valid.

    Proof

    \displaystyle\ (2n)^k+\binom{2n}{k+1}\ \le\ 2n(2n)^k\ ?

    \displaystyle\binom{2n}{k+1}\ \le\ (2n-1)(2n)^k

    \displaystyle\frac{[2n]!}{[2n-(k+1)]![k+1]!}\ \le\ (2n-1)(2n)(2n)(2n)....

    \displaystyle\frac{(2n)(2n-1)(2n-2)....}{(k+1)!}\ \le\ (2n-1)(2n)(2n)(2n)....

    There are k+1 terms in the numerator of the LHS and k+1 terms on the RHS, since there are k occurances of 2n.

    It's easy to see that the inequality holds.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Jun 2007
    Posts
    63
    thanks!
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Dec 2009
    Posts
    3,120
    Thanks
    1
    The proof is then complete when you examine the base case for k=2, assuming k is an integer.

    \displaystyle\ 1+\binom{2n}{1}+\binom{2n}{2}\ \le\ (2n)^2\ ?

    \displaystyle\ 1+2n+\frac{2n(2n-1)}{2}\ \le\ 4n^2\ ?

    \displaystyle\ 1+2n+n(2n-1)\ \le\ 4n^2\ ?

    1+2n+2n^2-n\ \le\ 4n^2\ ?

    2n^2+n+1\ \le\ 4n^2\ ?

    n+1\ \le\ 2n^2\ ?

    n(2n-1)\ \ge\ 1\ ?

    \text{\footnotesize\ True for \;\;}n\ \ge\ 1
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Binomial Inequality - Combinatorial Proof?
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: January 24th 2011, 02:34 PM
  2. Another combinatorial proof
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: July 5th 2010, 06:23 AM
  3. combinatorial sum
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: May 12th 2009, 10:46 AM
  4. Combinatorial Analysis
    Posted in the Pre-Calculus Forum
    Replies: 1
    Last Post: April 5th 2009, 10:18 AM
  5. Combinatorial proof
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: May 8th 2008, 11:45 PM

Search Tags


/mathhelpforum @mathhelpforum