Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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)$.

share|improve this question
Here is a related answer of mine. Does it answer your question, or are you looking for more information? –  Srivatsan Jan 30 '12 at 14:18
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? –  hardmath Jan 30 '12 at 14:19
Srivastan: I'm not sure whether the sum of b.c. is relevant to what I'd like to know. –  Pteromys Jan 30 '12 at 14:50
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. –  Pteromys Jan 30 '12 at 14:56
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$. –  Henry Jan 30 '12 at 15:05

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.