Bounding one binomial coefficient with another For given $n$ and $m$, I am interested in finding an expression for the smallest $r$ such that the following holds:
${r \choose m} \geq \frac{1}{2} {n \choose m}$.
Is such an expression, or at least an upper bound on such an $r$ feasible and if so, how would one start deriving it?
 A: Here are three results.


*

*If $r\ge n$ then $\binom rm \ge \frac12 \binom nm$.

*If $n<2m$ and $\binom rm \ge \frac12 \binom nm$ then $r\ge n$.

*If $r \ge n\big/\big(1+\frac{c}{m}\big)$ and $r\ge m$ then $\binom rm\ge \frac12\binom nm$, where $c = \frac{e-1}{e}\log 2 \approx 0.4382$.


Number 1 is the most obvious sufficient condition on $r$.  Number 2 is a partial converse of number 1, or, if you prefer, a demonstration that number 1 is sharp — and it indicates the relevance of the relative sizes of $n$ and $m$.  Number 3 is an improvement of number 1 when $m\le c(n-1)$.
Proof of 1.  $\binom nm$ is increasing in $n$.
Proof of 2.  Since $n<2m$, we have $\binom{n-1}{m} < \binom{n-1}{m-1}$, and so
$$ \binom{n-1}{m}
< \frac12 \left(\binom{n-1}{m}+\binom{n-1}{m-1}\right)
= \frac12 \binom{n}{m} \le \binom rm$$
whence $n-1 < r$.
Proof of 3.  If $r\ge n$, apply 1.  Assume $r<n$.
\begin{align*}
\frac{\binom rm}{\binom nm}
&= \prod_{k=0}^{m-1} \frac{r-k}{n-k} \\
&= \prod_{k=0}^{m=1} \left(1 - \frac{n-r}{n-k}\right) \\
&\ge \exp\left(\sum_{k=0}^{m-1} \frac{-\frac{n-r}{n-k}}{1-\frac{n-r}{n-k}} \right) &&\text{(a); see below} \\
&= \exp\left(-(n-r)\sum_{k=0}^{m-1} \frac1{r-k}\right) \\
&= \exp\left(-(n-r)\sum_{j=r-m+1}^{r} \frac1j\right) \\
&\ge \exp\left(-(n-r)\int_{r-m}^{r} \frac1x\,dx\right) \\
&= \left(\frac{r}{r-m}\right)^{-(n-r)} \\
&= \left(1 - \frac mr\right)^{n-r} \\
&\ge \exp\left(-\frac{e}{e-1}\cdot\frac{m(n-r)}{r}\right) &&\text{(b); see below} \\
&= \exp\left(-\frac{em}{e-1}\left(\frac nr - 1\right)\right) \\
&\ge \frac12
\end{align*}
using $r\ge\frac{n}{1+\frac cm}$ in the last step.
Proof of (a): Using the inequality $1+x\ge e^{x/(1+x)}$, which is valid for $x>-1$.  (This follows from $1+u\le e^u$ by taking $u=-x/(1+x)$.)
Proof of (b): Since $x\mapsto e^{-x}$ is convex, it lies below its secant line from $(0,1)$ to $(1,\frac1e)$; that is, $e^{-x}\le 1-\frac{e-1}{e} x$.  Replace $x$ with $\frac{e}{e-1} x$.
