# Asymptotic analysis with combination $\frac{{n \choose k}2^k}{{2n \choose k}} \ge \frac{1}{2}$

Consider the following inequality:

$$\frac{{n \choose k}2^k}{{2n \choose k}} \ge \frac{1}{2}$$

I would like to know how fast does the largest $k$ grow as $n$ grows, in order words, i want to find the function $f$ where: $$k = O(f(n))$$

What I did was I wrote a python programs and for each $n$ I iterate through $k$ and this is what I got: enter image description here

It seems like $k = O(\sqrt{n})$, but I'm not sure how to confirm it, I have a limited math background and I'm not even sure what branch of mathematics I should look into :).

EDIT: please don’t be too generous to give me a full solution, I would love to work it out myself with the right tools in hand :)

• Are you asking for the largest $k$ such the inequality holds for some given $n$? Have you looked at Stirling's formula? – saulspatz Jul 10 '18 at 21:51
• The smallest such $k$ is $0$ – saulspatz Jul 10 '18 at 22:58
• @saulspatz my apology, you were right, I was indeed looking for the largest $k$, I have fixed my question accordingly. – Chunxiao Li Jul 10 '18 at 23:03
Since you've expressed interest in a hint, here's a pointer down one path: Let's look at the ratio of binomials here. We have $\dfrac{2n\choose k}{n\choose k}$ $=\dfrac{\frac{(2n)!}{k!(2n-k)!}}{\frac{n!}{k!(n-k)!}}$ $=\dfrac{(2n!)(n-k!)}{n!(2n-k)!}$ $=\dfrac{(2n)\cdot(2n-1)\cdots(2n-k+1)}{n\cdot{n-1}\cdots(n-k+1)}$ $=\prod_{i=0}^{k-1}\dfrac{2n-i}{n-i}$. Now, distribute your $k$ factors of $2$ into the denominator here, simplify the individual terms of the product, and take logs; you should notice that you can massage this to look a lot like a Riemann sum. From there you can use Euler-Maclaurin or something similar to get an approximation to the sum and an error term, and this should be good enough for getting an asymptotic order on the appropriate $k$.