Lower bound on $p$ that satisfies ${p \choose n} \geq c$

Question

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?

Answer 1

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