In my paper "On Littlewood's estimate for the binomial distribution", Adv. Appl. Prob., 21 (1989) 475-478, copy at http://cs.anu.edu.au/~bdm/papers/littlewood2.pdf , I find sharp exact bounds on this sum. Taking $p=1/2$ in Theorem 2 gives:

$$B(k; n,1/2) = \sigma \cdot b(k-1,n-1,{1/ 2})\cdot Y({k-n/2\over \sigma})\cdot \exp({E(k; n,1/2)\over \sigma})$$

where:

• $b(k-1; n-1,1/2) = {1\over 2^{n-1}}{n-1\choose k-1}$
• $B(k; n,1/2) = \sum_{j=k}^n b(j; n,1/2) = {1\over 2^n}\sum_{j=k}^n {n\choose j}$
• $Y(x) = Q(x)/\phi(x)$, where:
  • $\phi(x) := {1\over \sqrt{2\pi}} e^{-x^2/2}$
  • $Q(x) := \int_{x}^\infty \phi(u) du $
• $E(k; n,1/2)$ is the error term, which lies between 0 and $\min(\sqrt{\pi/8}, {\sigma/(k-n/2)})$.
• $\sigma = \sqrt{n}/2$.

The relative error is at most $O(n^{-1/2})$ for all $k$, better if $k$ is not close to $n/2$.

Somewhere on the arXiv there is a paper making numerical comparisons of many such approximations. I can't find it just now, maybe someone else can.

In my paper "On Littlewood's estimate for the binomial distribution", Adv. Appl. Prob., 21 (1989) 475-478, copy at http://cs.anu.edu.au/~bdm/papers/littlewood2.pdf , I find sharp exact bounds on this sum. Taking $p=1/2$ in Theorem 2 gives:

$$B(k; n,1/2) = \sigma \cdot b(k-1,n-1,{1/ 2})\cdot Y({k-n/2\over \sigma})\cdot \exp({E(k; n,1/2)\over \sigma})$$

where:

• $b(k-1; n-1,1/2) = {1\over 2^{n-1}}{n-1\choose k-1}$
• $B(k; n,1/2) = \sum_{j=k}^n b(j; n,1/2) = {1\over 2^n}\sum_{j=k}^n {n\choose j}$
• $Y(x) = Q(x)/\phi(x)$, where:
  • $\phi(x) := {1\over \sqrt{2\pi}} e^{-x^2/2}$
  • $Q(x) := \int_{x}^\infty \phi(u) du $
• $E(k; n,1/2)$ is the error term, which lies between 0 and $\min(\sqrt{\pi/8}, {\sigma/(k-n/2)})$.
• $\sigma = \sqrt{n}/2$.

The relative error is at most $O(n^{-1/2})$ for all $k$, better if $k$ is not close to $n/2$.

The above requires $\frac n2\le k\le n$. For $0\le k\lt \frac n2$, use $B(k;n,p) = 1 − B(n-k+1; n, 1-p)$.

Somewhere on the arXiv there is a paper making numerical comparisons of many such approximations. I can't find it just now, maybe someone else can.

In my paper "On Littlewood's estimate for the binomial distribution", Adv. Appl. Prob., 21 (1989) 475-478, copy at http://cs.anu.edu.au/~bdm/papers/littlewood2.pdf , I find sharp exact bounds on this sum (take the case $p=1/2$ in Thm 2 for your problem). The relative error is at most $O(n^{-1/2})$ for all $k$, better if $k$ is not close to $n/2$.

Somewhere on the arXiv there is a paper making numerical comparisons of many such approximations. I can't find it just now, maybe someone else can.

In my paper "On Littlewood's estimate for the binomial distribution", Adv. Appl. Prob., 21 (1989) 475-478, copy at http://cs.anu.edu.au/~bdm/papers/littlewood2.pdf , I find sharp exact bounds on this sum. Taking $p=1/2$ in Theorem 2 gives:

$$B(k; n,1/2) = \sigma \cdot b(k-1,n-1,{1/ 2})\cdot Y({k-n/2\over \sigma})\cdot \exp({E(k; n,1/2)\over \sigma})$$

where:

• $b(k-1; n-1,1/2) = {1\over 2^{n-1}}{n-1\choose k-1}$
• $B(k; n,1/2) = \sum_{j=k}^n b(j; n,1/2) = {1\over 2^n}\sum_{j=k}^n {n\choose j}$
• $Y(x) = Q(x)/\phi(x)$, where:
  • $\phi(x) := {1\over \sqrt{2\pi}} e^{-x^2/2}$
  • $Q(x) := \int_{x}^\infty \phi(u) du $
• $E(k; n,1/2)$ is the error term, which lies between 0 and $\min(\sqrt{\pi/8}, {\sigma/(k-n/2)})$.
• $\sigma = \sqrt{n}/2$.

The relative error is at most $O(n^{-1/2})$ for all $k$, better if $k$ is not close to $n/2$.

Somewhere on the arXiv there is a paper making numerical comparisons of many such approximations. I can't find it just now, maybe someone else can.