Prove lower bound of binomial distribution near mean Let $0<p<1 / 2$ be fixed independently of $n,$ and let $X_{1}, \ldots, X_{n}$ be iid copies of a Bernoulli random variable that equals 1 with probability $p,$ thus $\mu_{i}=p$ and $\sigma_{i}^{2}=p(1-p),$ and so $\mu=n p$ and $\sigma^{2}=n p(1-p) .$ Using Stirling's formula  show that
$$
\mathbf{P}\left(\left|S_{n}-\mu\right| \geq \lambda \sigma\right) \geq c \exp \left(-C \lambda^{2}\right)
$$
for some absolute constants $C, c>0$ and all $\lambda \leq c \sigma .$ What happens when $\lambda$ is much larger than $\sigma ?$
Attempt: By substituting in Stirling formula, I have the following result, which in itself is a lower bound for binomial tail:
$\begin{aligned} P(\operatorname{Bin}(n, p)=&k)=\left(\begin{array}{l}n \\ k\end{array}\right) p^{k}(1-p)^{k} \\ &=\sqrt{\frac{n}{2 \pi k(n-k)}} \exp \left(o(1)+k \log \left(\frac{p}{1-p} \cdot \frac{n-k}{k}\right)+n \log \left(\frac{(1-p) n}{n-k}\right)\right) \\ &=\sqrt{\frac{n}{2 \pi k(n-k)}} \exp \left(o(1)-n\left(D_{K L}(k / n \| p)\right)\right) \end{aligned}$
Let $k=n p+\lambda \sqrt{n(1-p) p}$ where $\lambda=o\left(n^{\frac{1}{6}}\right) .$ Then, we can continue our approximation
$$
\begin{aligned}
=\sqrt{\frac{n}{2 \pi k(n-k)}} & \exp \left(o(1)+k \log \left(\frac{n-\lambda \sqrt{\frac{n p}{1-p}}}{n+\lambda \sqrt{\frac{n(1-p)}{p}}}\right)+n \log \left(\frac{n}{n-\lambda \sqrt{\frac{n p}{1-p}}}\right)\right) \\
&=\sqrt{\frac{n}{2 \pi k(n-k)}} \exp (o(1)\\
&+(n p+\lambda \sqrt{n(1-p) p})\left(-\frac{\lambda}{\sqrt{n}}\left(\sqrt{\frac{p}{1-p}}+\sqrt{\frac{1-p}{p}}\right)+\frac{1}{2} \frac{\lambda^{2}}{n}\left(\frac{1}{p}-\frac{1}{1-p}\right)\right.\\
&\left.\left.+O\left(\frac{\lambda^{3}}{n^{3 / 2}}\right)\right)+n\left(-\lambda \sqrt{\frac{p}{1-p}} \frac{1}{\sqrt{n}}-\frac{\lambda^{2}}{2} \frac{p}{1-p} \frac{1}{n}+o\left(\frac{\lambda^{3}}{n^{3 / 2}}\right)\right)\right) \\
&=\sqrt{\frac{n}{2 \pi k(n-k)}} \exp \left(o(1)-\frac{1}{2} \lambda^{2}\right)
\end{aligned}
$$
using Taylor's expansion.
Now I'm stuck. I'm trying to figure out how to get rid of $\sqrt{\frac{n}{2 \pi k(n-k)}}\sim O(1/\sqrt{n})$ in the front by summing up other terms from $k$ to $n$ but I don't know how to do that. Plus, I assumed $\lambda=o(n^{1/6})$ which is not part of the question. I saw most posts on this topic on this site. Don't think there is an answer to this particular form.
 A: The detailed calculations here answers a more general form of this question. In particular, we can use their Claim 1 (from Stirling's formula) to tackle this question more specifically:
$$
\binom{n}{k} \geq \frac{1}{e \sqrt{2 \pi k}} \left( \frac{n}{k} \right)^k \left( \frac{n}{n - k} \right)^{n - k} .
$$
Putting this in with $k = np + \lambda \sigma$ allows us to simplify some of the terms, say
$$
p^{np + \lambda \sigma} \left( \frac{n}{k} \right)^k = \left( \frac{np}{np + \lambda \sigma} \right)^{np + \lambda \sigma} = \left( 1 + \frac{\lambda \sigma}{np} \right)^{-(np + \lambda \sigma)} \approx \exp\left( -\frac{\lambda \sigma}{np} (np + \lambda \sigma) \right) = \exp\left( -\lambda \sigma - \frac{\lambda^2 \sigma^2}{np} \right) .
$$
Note that $\sigma^2 = np(1-p)$. For the other term, we can similarly check that
$$
(1-p)^{n-k} \left( \frac{n}{n - k} \right)^{n-k} \approx \exp\left( \frac{\lambda \sigma}{n(1-p)} (n(1-p) - \lambda \sigma) \right) = \exp\left( \lambda \sigma - \frac{\lambda^2 \sigma^2}{n(1-p)} \right) .
$$
So we can combine these to estimate the terms tail probability
$$
\mathbb{P}(S_n \geq \mu + \lambda \sigma) = \sum_{k=np + \lambda \sigma}^{n} \binom{n}{k} p^k (1-p)^{n-k} .
$$
Note that the probability distribution of the Binomial $S_n$ is decreasing past its mean. To deal with the $1/\sqrt{k}$ term that will come from Stirling's, we may want to lower bound this sum by taking only the first, say, $\sigma$ terms (which is of order $\sqrt{n}$). To make sure we don't overshoot, we require $np + \lambda \sigma + \sigma \leq n$; having $\lambda \sigma \leq cn$ will be sufficient for some appropriate constant $c$. Thus, we have the lower bound
$$
\mathbb{P}(S_n \geq \mu + \lambda \sigma) \geq \sigma \cdot \frac{c'}{\sqrt{np + 2\lambda \sigma}} \cdot \exp\left( -\frac{(\lambda^2}{p(1-p)} \right) \geq c'' \exp(-C \lambda^2) ,
$$
for some absolute constants $c, c'', C > 0$.
