0
$\begingroup$

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

sorry for bad english :D

3 Answers 3

5

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

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

1

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?