1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Binomials and Proof by Induction

  1. Sep 23, 2012 #1
    1. The problem statement, all variables and given/known data

    Prove (n choose k) ≤ ((en)/k)^k by induction on k.

    2. Relevant equations

    I can't of anything that's awfully relevant besides the general steps of induction.

    3. The attempt at a solution

    So I found it true for the k=1 case which was easy enough. Then assumed true the k case. And now have to prove the k+1 case.

    So after working on the problem for awhile, I arrived at
    ((n-k)/(k+1)) * (n choose k) ≤ ((en)/k)^k * ((n-k)/(k+1))

    but from here I'm stuck and not sure how to deconstruct the (n choose k) into something workable, let alone construct (n choose k+1). any help would be greatly appreciated.
     
  2. jcsd
  3. Sep 23, 2012 #2
    I'm not sure I understand the notation. What is "en"?
     
  4. Sep 23, 2012 #3
    the Euler number, e=2.718 or something i think. so en is e*n
     
  5. Sep 24, 2012 #4

    Ray Vickson

    User Avatar
    Science Advisor
    Homework Helper

    It might be helpful to note that
    [tex] {n \choose k} = \frac{n (n-1) \cdots (n-k+1)}{k!}
    = \frac{n^k (1 - \frac{1}{n})(1 - \frac{2}{n}) \cdots (1 - \frac{k-1}{n})}{k!},[/tex] and you can further bound the numerator and denominator.

    RGV
     
  6. Sep 24, 2012 #5

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    Then you mean e^n. "en" and "e*n" would be e times n.
     
  7. Sep 24, 2012 #6
    no i mean e times n. hence en or e*n.
     
  8. Sep 24, 2012 #7
    i under the bound for the numerator, but i dont understand how to bound the denominator?
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Binomials and Proof by Induction
Loading...