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 :)

Thanks in advance!

  • $\begingroup$ Are you asking for the largest $k$ such the inequality holds for some given $n$? Have you looked at Stirling's formula? $\endgroup$ – saulspatz Jul 10 '18 at 21:51
  • $\begingroup$ I'm pretty sure this is related to the birthday paradox $\endgroup$ – msm Jul 10 '18 at 22:42
  • $\begingroup$ The smallest such $k$ is $0$ $\endgroup$ – saulspatz Jul 10 '18 at 22:58
  • $\begingroup$ @saulspatz my apology, you were right, I was indeed looking for the largest $k$, I have fixed my question accordingly. $\endgroup$ – Chunxiao Li Jul 10 '18 at 23:03
  • $\begingroup$ @saulspatz And I missed the Stirling's formula part, I will read it up, thanks! $\endgroup$ – Chunxiao Li Jul 10 '18 at 23:15

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$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.