Big Omega notation and binomial coefficients

Question

Closed. This question does not meet Mathematics Stack Exchange guidelines. It is not currently accepting answers.

---

Please provide additional context, which ideally explains why the question is relevant to you and our community. Some forms of context include: background and motivation, relevant definitions, source, possible strategies, your current progress, why the question is interesting or important, etc.

Closed 9 months ago.

Improve this question

Let $x = \frac{3n}{10}$ and $y = \frac{n}{5} – 1$. Can you explain to me why $\frac{n \choose x}{ n \choose y} \geq \Omega(\alpha^n)$, for some $\alpha \geq 1$ ?

I tried to use Stirilings formula, but I'm not sure how to do it.

Answer 1

$$\frac{{n \choose x}}{{n \choose y}} = \frac{n!y!(n-y)!}{n!x!(n-x)!} = \frac{(0.2n-1)!(0.8n+1)!}{(0.3n)!(0.7n)!}$$

Now use Stirling's approximation bound of

$$\sqrt{2\pi}n^{n+\frac 12}e^{-n} \leq n! \leq en^{n+\frac 12}e^{-n}$$

to get:

$$\frac{(0.2n-1)!(0.8n+1)!}{(0.3n)!(0.7n)!} \geq \frac{2\pi \left((0.2n-1)^{(0.2n-0.5)}e^{-0.2n+1} \right)\times\left((0.8n+1)^{(0.8n+1.5)}e^{-0.8n-1} \right)}{e^2 (0.3n)^{0.3n+0.5}e^{-0.3n}(0.7n)^{0.7n+0.5}e^{-0.7n}} =f(n)$$

Now calculate $\frac{\log(f(n))}{n}$ to get

$$\Delta(n)=\frac{\log (f(n))}{n} = \frac{0.618201}{n} - \frac{0.5 \log(0.2 n - 1)}{n} + 0.2 \log(0.2 n - 1) + \frac{1.5 \log(0.8 n + 1)}{n} + 0.8 \log(0.8 n + 1) - \frac{\log n}{n} - \log(n) + 0.610864$$

Now verify that for $n\geq 6, \Delta(n)\geq 0.11$

Which implies $f(n)\geq e^{0.11n} \geq 1.11^n$