# Probabilistic Method – 5

Q.1. Prove that ${2m \choose m} \geq \frac{2^{2m}}{4 \sqrt{m} + 2}.$

Solution.

Toss an unbiased coin $2m$ times with the coin tosses being independent. Let $X$ denote the number of heads in the coin tosses.

$\therefore E[X] = m; \mbox{ } Var [X] = m/2.$

$Pr[ | X - E[X] | < \sqrt{m} ] \geq 1 - 1/2 = 1/2.$ (using Chebyshev’s inequality) $\ldots (1)$

Also, $Pr[ \mbox{ exactly k heads occur} ] = { 2m \choose k} 2^{-2m} \leq {2m \choose m} 2^{-2m}.$ (because ${2m \choose m} \geq { 2m \choose k}$ for all possible $k$ )

$\therefore Pr[ | X - E[X] | < \sqrt{m} ] \leq (2 \sqrt{m} + 1) { 2m \choose m} 2^{-2m}.$ $\ldots (2)$

Combine (1) and (2) to get the desired result.

$-$