Search code examples
algorithmmathbig-obinomial-coefficients

How to prove binomial coefficient is asymptotic big theta of two to the power n?

I am stuck at this problem. I think it is equivalent to show 2m choose m is big theta of 4 to the power n, but still find difficult to prove it.

enter image description here

Thanks of @LutzL's suggestion. I thought of stirling's approximation before. enter image description here

Solution

  • The O-part should be easy. Choosing exactly n/2 elements out of n is a special case of choosing arbitrary combinations out of n elements, i.e. deciding for each of these n elements whether to choose it or not.

    The Ω-part is harder. In fact, plotting 4n / binomial(2 n, n) for moderately large n I see no indication that this would flatten to stay below some constant. Speaking intuitively, the larger n is, the more special is the case when you take a random pick from n elements and coincidentially happen to choose exactly n/2 of them. That probability should tend to zero as n increases, meaning that 2n should always grow faster than n choose n/2. Are you certain you understood this part of your task correctly?