1. This site uses cookies. By continuing to use this site, you are agreeing to our use of cookies. Learn More.

Hard Math Problem

Discussion in 'BlackHat Lounge' started by fusilli_jerry89, Oct 16, 2009.

  1. fusilli_jerry89

    fusilli_jerry89 Regular Member

    Joined:
    Dec 7, 2008
    Messages:
    280
    Likes Received:
    40
    just wondering if anyone knows how to do this?

    Show that nCk >= (n/k)^k

    That is, show that n chose k is greater than or equal to (n/k)^k


    Any ideas?
     
  2. im n0t lurer

    im n0t lurer Regular Member

    Joined:
    Jun 29, 2009
    Messages:
    229
    Likes Received:
    54
    no sorry, you best bet would be to try make a triangel with 4 angles.. XD

    btw what kind of math is that lol?
     
  3. oxonbeef

    oxonbeef BANNED BANNED

    Joined:
    Jan 4, 2009
    Messages:
    2,242
    Likes Received:
    7,872
    the proof of binomial coefficient


    (x+y)^n = sum(k=0,n, nCk x^(n-k) y^k)

    and we want to show that:

    nCk = (n!)/(n-k)!k!

    is true. So let's use induction on n.

    Base case: n = 1. (x+y)^1 = x+y, so 1C0 = 1C1 = 1!/1!0! = 1!/0!1!.

    Inductive step: suppose nCk = (n!)/(n-k)!k! for some n and all 0 ≤ k ≤ n. We'll show it's true for n+1 and all 0 ≤ k ≤ n+1. So

    (x+y)^(n+1) = (x+y)(x+y)^n = (x+y)sum(k=0,n, nCk x^(n-k) y^k)

    So multiply through and note that the coefficient on x^(n+1-k) y^k is:

    for k = 0: 1 = (n+1)!/(n+1)!0!
    for k = n+1: 1 = (n+1)!/0!(n+1)!
    for 1 ≤ k ≤ n: nCk + nC(k-1)

    So we want to show that nCk + nC(k-1) = (n+1)!/(n+1-k)!k!. So:

    n!/(n-k!)k! + n!/(n+1-k)!(k-1)! = [n!(n+1-k)+n!k]/(n+1-k)!k! = n!(n+1)/(n+1-k)!k! = (n+1)!/(n+1-k)!k!

    2+2=?+google
     
    • Thanks Thanks x 1
    Last edited: Oct 16, 2009
  4. matapples01

    matapples01 Regular Member

    Joined:
    May 15, 2008
    Messages:
    358
    Likes Received:
    208
    Sorry, I only know "old math" where the problems are all numbers. :eek: