how prove $\binom{n}{n/2} = \Omega (\frac{2^{n}}{n})$?

Question

how can prove $\binom{n}{n/2} = \Omega (\frac{2^{n}}{n})$ ? it s for algorithms coures .

sorry for bad english :D

Answer 1

Hint: What is the sum of $\binom{n}{k}$ for all $k$? And which is the greatest of these?

Answer 2

An alternative is to use Stirling's formula to get $$\binom{n}{n/2} = \Theta\left(\frac{2^n}{\sqrt{n}}\right).$$

You can also get the same result from the Central Limit Theorem, since $$\frac{\binom{n}{n/2}}{2^n} = \mathrm{Pr}[\mathrm{Bin(n,\frac{1}{2})}=\frac{n}{2}].$$

Answer 3

Regard all the binomial coefficients $\binom n0, \binom n1, \dots, \binom nn$.

How many are there?

What is their sum?

What is the maximal element in this list?

What is the minimal size of a maximal element in a list with A elements and sum S?