# how to prove $\sum _{|k|\lt\sqrt m}\binom{2m}{m+k}\ge2^{2m-1}$

how to prove $$\sum _{|k|\lt\sqrt m}\binom{2m}{m+k}\ge2^{2m-1},\forall m\ge1$$ Thanks in advance .

-

Consider tossing a fair coin $2m$ time and let $X$ count the number of heads. Then from Chebyshev inequality, we have that $$\mathbb{P}(\vert X - m\vert \geq k \sqrt{m/2}) \leq \dfrac1{k^2}$$ Take $k =\sqrt{2}$, to get that $$\mathbb{P}(\vert X - m\vert \geq \sqrt{m}) \leq \dfrac12, \,\,\, \text{i.e., }\,\,\, \mathbb{P}(\vert X - m\vert < \sqrt{m}) \geq \dfrac12$$ Hence, we have $$\sum_{\vert k \vert <\sqrt{m}} \dfrac{\dbinom{2m}{m+k}}{2^{2m}} \geq \dfrac12$$ which gives us $$\sum_{\vert k \vert <\sqrt{m}} \dbinom{2m}{m+k} \geq 2^{2m-1}$$
@AlanH Note that $X$ can take values only from $1,2,3,\ldots,2m$. We need $\vert X - m \vert < \sqrt{m} \implies X$ can take values take integers in the domain $(m-\sqrt{m}, m+\sqrt{m})$. Since $X$ is binomial random variables, we have $$P(X = \ell) = \dfrac1{2^{2m}} \dbinom{2m}{\ell}$$ Hence, $$P(\vert X - m \vert < \sqrt{m}) = P(X = m-\lfloor \sqrt{m} \rfloor + 1) + P(X = m-\lfloor \sqrt{m} \rfloor + 2) + \cdots + P(X = m+\lceil \sqrt{m} \rceil - 1)$$ – user17762 Mar 24 '13 at 6:43