lower bound on sum of Bernoulli trials Suppose that $X$ is the sum of $n$ Bernoulli random variables with $p=1/2$.
I'm wondering whether there a way to get a function $f(n,k)$ such that, for $k\ge 0$, $$Pr[X \ge E[X] + k ] \ge f(n,k).$$
I've looked at Markov's Inequality, but this works the opposite way as it gives me a lower bound of being close to the mean.
 A: Exact formulas for $\mathbb P(X\geqslant \mathbb E(X)+k)$ involve sums of binomial coefficients which, except in the regime $\frac{n}2-k$ bounded, may not be very illuminating. On the other hand, the exact asymptotics of  $\mathbb P(X\geqslant \mathbb E(X)+k)$ when $n\to\infty$ and $k=\Theta(n)$ are known to correspond to the optimal exponential inequality. Let us explain this in the present case. For every $s\geqslant1$, 
$$
\mathbb P(X\geqslant \mathbb E(X)+k)\leqslant\mathbb E(s^X)s^{-\mathbb E(X)-k}.
$$
One knows that $\mathbb E(s^X)=[\frac12(1+s)]^n$ and $\mathbb E(X)=\frac12n$, hence the task is to minimize the quantity $(1+s)^ns^{-(n/2)-k}$ over $s\geqslant1$. The logarithmic derivative is $\frac{n}{1+s}-\frac{(n/2)+k}{s}$, hence one chooses $s=\frac{(n/2)+k}{(n/2)-k}$, which yields $\mathbb P(X\geqslant \mathbb E(X)+k)\leqslant f(n,k)$ with
$$
f(n,k)=\left(1-\tfrac{2k}n\right)^{-\frac{n}2+k}\left(1+\tfrac{2k}n\right)^{-\frac{n}2-k}.
$$
As said above, if $n\to\infty$ and $k/n\to\alpha$, then it happens that this upper bound also indicates the correct logarithmic behaviour of the probability considered, since
$$
\lim\limits_{n\to\infty}n^{-1}\log\mathbb P(X\geqslant \mathbb E(X)+k)=\lim\limits_{n\to\infty}n^{-1}\log f(n,\alpha n).
$$
For example,
$$
f(n,\tfrac{n}4)=\left(\tfrac{16}{27}\right)^{\tfrac{n}4},
$$
hence
$$
\mathbb P(X\geqslant\tfrac{3n}4+o(n))=\left(\tfrac{16}{27}\right)^{\tfrac{n}4+o(n)}.
$$
A: For integers $j$ with $0 \le j \le n$,
$$Pr[X \ge j] = 2^{-n} {n \choose j} {\mbox{$_2$F$_1$}(1,-n+j;\,j+1;\,-1)}$$ 
