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:
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 :)
Thanks in advance!
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$.