How to prove an inequality of quotients of 2 combinations I ran into a question in paper reading of 
Robust Uncertainty Principles: Exact Signal Reconstruction From Highly Incomplete Frequency Information
On page 5, there's an inequality 
\begin{equation}
\frac{\binom{N-\sqrt N}{|\Omega|}}{\binom{N}{|\Omega|}} \geq (1-\frac{2|\Omega|}{N})^{\sqrt N}
\end{equation}
with assumption 
$|\Omega| > \sqrt N$
We can assume $\sqrt N$ is a integer. 
Thanks. 
 A: If you just expand the combinations you can get a stronger result.  I will leave the absolute value bars off $\Omega$ as we are given $\Omega \gt 0$
$$\begin{align}
\frac{\binom{N-\sqrt N}{|\Omega|}}{\binom{N}{|\Omega|}} &=\frac {(N-\sqrt N)!\Omega!(N-\Omega)!}{(N-\sqrt N-\Omega)!\Omega!N!}\\
&=\frac{(N-\Omega)(N-\Omega-1)\ldots (N-\Omega-\sqrt N+1)}{N(N-1)(N-2)\ldots N-\sqrt N+1)}\\
&= \left(1-\frac \Omega N\right)\left(1-\frac \Omega {N-1}\right)\left(1-\frac \Omega {N-2}\right)\ldots \left(1-\frac \Omega {N-\sqrt N+1}\right)\\
&\geq (1-\frac{\Omega}{N})^{\sqrt N}
\end{align}$$
A: More generally, it is true that
$$ \frac{\binom{n-k}{r}}{\binom{n}{r}} \ge \bigl( 1 - \frac{2r}{n} \bigr)^r $$
whenever $r \ge k$. Taking $k = \sqrt{N}$, $r = |\Omega|$ gives the stronger lower bound $\bigl( 1 - \frac{2|\Omega|}{N} \bigr)^{|\Omega|}$.
Proof. The left-hand side is
$$ \frac{(n-k)(n-k-1) \ldots (n-k-r+1)}{n(n-1) \ldots (n-r+1)} =
\frac{\bigl( 1 - \frac{k}{n} \bigr)}{1} \frac{\bigl( 1 - \frac{k+1}{n} \bigr)}{\bigl( 1 - \frac{1}{n} \bigr)} \ldots \frac{\bigl( 1 - \frac{k+r-1}{n} \bigr)}{\bigl( 1 - \frac{r-1}{n}\bigr)}.$$
Now use that $1- \frac{k+j}{n} \ge 1 - \frac{2r}{n}$ if $j \le r$ and $\bigl( 1 - \frac{j}{n} \bigr)^{-1} \ge 1$.
