4
$\begingroup$

How fast does $\binom{n}{k}$, $n$ fixed, grow when $k \le n/2$?

Especially, I'm interested in the growth of the "inverse" of binomial coefficient $B_n(x) := \min \{k:\binom{n}{k} \ge x\}$.

EDIT: This was answered in a previous post, according to which $B_n(x) = O(\log x)$.

  • 1
    Here is a related [answer of mine](http://math.stackexchange.com/a/64270). Does it answer your question, or are you looking for more information?2012-01-30
  • 1
    One approach to such a question would be to give the slope of the approximation afforded by a normal distribution to the binomial. Another would be more exact, presenting the slope between (or ratio of) two consecutive binomial coefficients. Does one or the other of these approaches better fit your intended application?2012-01-30
  • 0
    Srivastan: I'm not sure whether the sum of b.c. is relevant to what I'd like to know.2012-01-30
  • 0
    hardmath: My application of the analysis of an algorithm whose inner loop is run $B_n(x)$ times. So, as you've said, the ratio or difference between two consecutive terms is a good measure, but it doesn't fit my application well. By the way, $x$ is much smaller than a typical value of $\binom{n}{k}$, so what I'd like to know is the growth of $\binom{n}{k}$ when $k$ is small.2012-01-30
  • 4
    On your initial question, $$\dfrac{\binom{n}{k}}{\binom{n}{k-1}} = \dfrac{n-k}{k} = \dfrac{n}{k}-1$$ which grows faster when $k$ is small, and is close to $1$ when $k$ is close to $n/2$.2012-01-30
  • 0
    This seems to be a duplicate. Although note: I choose the wrong link when I voted to close.2012-01-31

0 Answers 0