2
$\begingroup$

Suppose I have $${p \choose n} \geq c$$ for constant positive integers $n,c$. How can I get a good lower bound on $p$? In other words, how large do I have to make the upper index of the binomial coefficient to make it greater than a constant?

$\endgroup$
  • 2
    $\begingroup$ You could try using Stirling's approximation $\sqrt{2\pi}n^{n+1/2}e^{-n+1/(12n+1)}\leq n!\leq \sqrt{2\pi}n^{n+1/2}e^{-n+1/(12n)}$ $\endgroup$ – Michael Burr Nov 30 '16 at 17:51
  • $\begingroup$ Stirling is asymptotic, but if you round it to the nearest integer it is correct once $n$ is only 5 or 6 (pretty small at least). $\endgroup$ – TravisJ Nov 30 '16 at 18:26
2
$\begingroup$

Naively using Stirling turns out to be the wrong way to go. It turns out, however, that there is a very simple solution, though it gives a very poor bound. Namely, take the log of both sides:

$$ \begin{align*} \sum_{i=1}^n \left[ \log{\frac{(p-n)+i}{i}} \right] &\geq \log{c} \end{align*} $$ Now here's where we leave the land of perfection and find a lower bound that is not necessarily optimal. Namely, we note that if the largest term of the sum is equal to $\frac{\log{c}}{n}$, then certainly the sum itself is less than or equal to $\log{c}$. So it is sufficient to just look at the largest term and try to find a $p_t$ that makes it equal to $\frac{\log{c}}{n}$. $p_t$ will then be a lower bound on $p$. It's easy to show that the largest term is the $i=1$ term, so we have: $$\log{\frac{(p_t-n)+1}{1}} = \frac{\log{c}}{n}$$ Now take the exponential of both sides and solve for $p_t$: $$ \begin{align*} \frac{(p_t-n)+1}{1} &= c^{1/n} \\ p_t &= n + c^{1/n} - 1 \end{align*} $$ With our bound then being $p \geq \left\lceil n + c^{1/n} - 1 \right\rceil$. This bound clearly isn't optimal (for example, when $1<c<n^n$ it just gives the naive bound $p > n$, which is only optimal for $c \leq n$), but for huge $c$ it does beat the naive bound. So that's something.

It's worth pointing out that if you take the smallest term instead of the largest, you get an upper bound, namely $p_t < nc^{1/n}$. Which is less than $2n$ if $c<n^n$. So the naive bound is 2-optimal for reasonably small $c$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.