A binomial tail sum inequality Let $n$ be a positive even integer and $x_1,..,x_n$ be iid, $\mathop{Bernoulli}(\frac{1}{2})$ random variables. Let $S_n = x_1 + .. + x_n$. Let $0\leq k \leq \frac{n}{2}$ be an integer.
By Hoeffding's inequality, $$\text{Pr}\left[S_n-\frac{n}{2}\geq k\right] \leq e^{-\frac{2k^2}{n}}$$
Hence, we have
$$ 
\binom{n}{\frac{n}{2}+k} + \binom{n}{\frac{n}{2}+k+1} + .. + \binom{n}{n} \leq 2^{n}e^{-\frac{2k^2}{n}}
$$
Is there a direct proof for this inequality?
 A: $S_n$ is a sum of $n$ i.i.d Bernoulli random variables with each $x_i\sim Bernoulli(\frac{1}{2})$ (according to what you wanted to prove). Then $S_n\sim Binomial(n,\frac{1}{2})$ and $\mathbb E[S_n]=\frac{n}{2}$.
Now, let's evaluate $\mathbb P\left[S_n-\frac{n}{2}\geq k\right]$ :
\begin{align*}
\mathbb P\left[S_n-\frac{n}{2}\geq k\right]&=\mathbb P\left[S_n\geq k+\frac{n}{2}\right]\\
&=\sum_{k=0}^{n/2} \mathbb P\left[S_n= k+\frac{n}{2}\right]\\
&=\sum_{k=0}^{n/2} \binom{n}{k+\frac{n}{2}}\left(\frac{1}{2}\right)^{k+\frac{n}{2}}\left(\frac{1}{2}\right)^{n-k-\frac{n}{2}}\\
&=\frac{1}{2^n}\sum_{k=0}^{n/2} \binom{n}{k+\frac{n}{2}}\left(\frac{1}{2}\times2\right)^{k+\frac{n}{2}}\\
&=\frac{1}{2^n}\sum_{k=0}^{n/2} \binom{n}{k+\frac{n}{2}}\\
\end{align*}
On the other hand, using Markov's inequality $\forall s>0, \forall k\in\{0,...,\frac{n}{2}\}$, and the independence of $x_i$ :
\begin{align*}
\mathbb P\left[S_n-\frac{n}{2}\geq k\right]&=\mathbb P\left[e^{s(S_n-\frac{n}{2})}\geq e^{sk}\right]\\
&\leq \dfrac{\mathbb E\left[e^{s(S_n-\frac{n}{2})}\right]}{e^{sk}}\\
&\leq e^{-sk}e^{-\frac{sn}{2}}\mathbb E\left[e^{s(S_n)}\right]\\
&\leq e^{-sk}e^{-\frac{sn}{2}}\left(\frac{e^s+1}{2}\right)^n\\
&\leq \frac{1}{2^n}\left[e^{s(-k-\frac{n}{2})}(e^s+1)^n\right]
\end{align*}
Since $k\in\{0,...,\frac{n}{2}\}$, then $(-2k)\geq(-\frac{n}{2}-k)$
$$\frac{1}{2^n}\left[e^{s(-k-\frac{n}{2})}(e^s+1)^n\right]\leq \frac{1}{2^n}\left[e^{s(-2k)}(e^s+1)^n\right]$$
This is the best I could do. Hope it helps a bit.
There's always (first answer) the direct use of Hoeffding's inequality :
$$ \mathbb P\left[S_n-\frac{n}{2}\geq k\right]=\frac{1}{2^n}\sum_{k=0}^{n/2} \binom{n}{k+\frac{n}{2}}\leq e^{\frac{-2k^2}{n}}$$
Mulitplying by $2^n$ gives us
$$ \sum_{k=0}^{n/2} \binom{n}{k+\frac{n}{2}}=\binom{n}{\frac{n}{2}+k} + \binom{n}{\frac{n}{2}+k+1} + .. + \binom{n}{n} \leq 2^n e^{\frac{-2k^2}{n}}$$
