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

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?

• 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)}$ – Michael Burr Nov 30 '16 at 17:51
• 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). – TravisJ Nov 30 '16 at 18:26

## 1 Answer

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