From the Berry Esseen theorem I know, that $$\sup_{x\in\mathbb R}|P(B_n \le x)-\Phi(x)|\in O\left(\frac 1{\sqrt n}\right)$$ whereby $B_n$ has the standardized binomial distribution and $N$ has the standardized normal distribution. I can prove this for $x\approx 0$ with Stirling's formula and a similar proof shown here.
Unfortunately Stirling's approximation becomes worse the bigger $|x|$ is, so that I can only provide that
$$\sup_{|x| \le c}|P(B_n \le x)-\Phi(x)|\in O\left(\frac 1{\sqrt n}\right)$$ for a fixed $c > 0$.
My question: Is there a good proof for $\sup_{|x| > c}|P(B_n \le x)-\Phi(x)|\in O\left(\frac 1{\sqrt n}\right)$? How can I estimate the error of the difference in the tail probability of the binomial distribution to the normal distribution?
Note: Chebyshev's inequality does not provide the right convergence speed. As zhoraster shows in his answer to Finding an error estimation for the De Moivre–Laplace theorem, also Chernoff's inequality does not provide the right convergence speed, too. That's why I am looking for another method. I also want to use more easy and direct approximations than Stein's method which is used in the proof of the Berry Esseen theorem.
Update: I reasked this question on MO, see https://mathoverflow.net/questions/220030/normal-approximation-of-tail-probability-in-binomial-distribution
Best Answer
See the answer on mathoverflow.com by Iosif Pinelis.