Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Prove: the biggest that N choose k gets is at k = N/2 for N even

  1. Oct 22, 2013 #1
    Is there a simple way to prove this? I tried to use induction, but you get down to some horrible fraction (letting [itex]N = 2m[/itex] for some [itex]m[/itex]) in the inductive step:

    [tex]
    \begin{pmatrix} 2(m+1) \\ k \end{pmatrix} = \frac{(2m)!}{k!(2m - k)!} \cdot \frac{(2m+2)(2m+1)}{(2m+2-k)(2m+1-k)}
    [/tex]

    The inductive hypothesis is to assume the thing on the left is biggest for [itex]k = m[/itex], but the second fraction gets bigger as you make [itex]k[/itex] bigger. So...what to do! Any comments? Thanks!
     
  2. jcsd
  3. Oct 22, 2013 #2
    Try to prove this: If ##k<k^\prime\leq N/2##, then

    [tex]\binom{N}{k} < \binom{N}{k^\prime}[/tex]

    And if ##N/2\leq k^\prime<k##, then

    [tex]\binom{N}{k} < \binom{N}{k^\prime}[/tex]

    To prove these two statements, it suffices to look at ##k## and ##k+1##.
     
  4. Oct 22, 2013 #3

    Erland

    User Avatar
    Science Advisor

    Note that it suffices to show that k!(2m-k)! attains its minimum at k=m (0≤k≤2m), and this is equivalent to showing that
    (m-r)!(m+r)! attains its minimum at r=0 (0≤r≤m).
     
  5. Oct 23, 2013 #4

    BTP

    User Avatar

    let n=even, k<=n/2
    [tex]
    \begin{pmatrix} n \\ k \end{pmatrix} =\begin{pmatrix} n \\ k-1 \end{pmatrix} *{ (n-k+1)/(k)}
    [/tex]

    then (n-k+1)/k > (n/2 +1)/k >1

    QED

    ...the symmetry between k and n-k finishes the proof.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Prove: the biggest that N choose k gets is at k = N/2 for N even
Loading...