[proofplan]
We use the exponential moment method: exponentiate the tail event, bound its probability by the exponential moment of $S_n$, and then optimize the exponential parameter. The binomial moment generating function is computed exactly and bounded by $\exp\{\mu(e^\lambda-1)\}$. Choosing $\lambda=\log(1+\delta)$ gives the upper-tail multiplicative form, while choosing $\lambda=\log(1-\delta)$ and applying the same argument to a lower-tail event gives the lower-tail multiplicative form. The simplified estimates follow by proving two elementary logarithmic inequalities on $\delta \in (0,1)$.
[/proofplan]
[step:Compute and bound the exponential moment of the binomial variable]
Let $\lambda \in \mathbb{R}$. Since $S_n \sim \operatorname{Bin}(n,p)$, its probability mass function is
\begin{align*}
\mathbb P(S_n = k)=\binom{n}{k}p^k(1-p)^{n-k}
\end{align*}
for $k \in \{0,1,\dots,n\}$. Therefore
\begin{align*}
\mathbb E[e^{\lambda S_n}]=\sum_{k=0}^{n} e^{\lambda k}\binom{n}{k}p^k(1-p)^{n-k}.
\end{align*}
Rewriting the summand gives
\begin{align*}
\mathbb E[e^{\lambda S_n}]=\sum_{k=0}^{n} \binom{n}{k}(pe^\lambda)^k(1-p)^{n-k}.
\end{align*}
The [binomial theorem](/theorems/750) then yields
\begin{align*}
\mathbb E[e^{\lambda S_n}]=(1-p+pe^\lambda)^n=(1+p(e^\lambda-1))^n.
\end{align*}
The elementary inequality $1+x \leq e^x$ for $x \in [-1,\infty)$ applies to $x=p(e^\lambda-1)$, because $p \in [0,1]$ and $e^\lambda-1 \geq -1$. Hence
\begin{align*}
\mathbb E[e^{\lambda S_n}]
\leq
\exp\{np(e^\lambda-1)\}
=
\exp\{\mu(e^\lambda-1)\}.
\end{align*}
[/step]
[step:Choose $\lambda=\log(1+\delta)$ to prove the upper-tail bound]
Fix $\delta > 0$ and define $\lambda := \log(1+\delta)$. Then $\lambda > 0$ and $e^\lambda = 1+\delta$. Since the map $t \mapsto e^{\lambda t}$ is increasing on $\mathbb{R}$,
\begin{align*}
\{S_n \geq (1+\delta)\mu\}
\subset
\{e^{\lambda S_n} \geq e^{\lambda(1+\delta)\mu}\}.
\end{align*}
For the non-negative [random variable](/page/Random%20Variable) $e^{\lambda S_n}$, the inequality
\begin{align*}
\mathbb P(e^{\lambda S_n} \geq e^{\lambda(1+\delta)\mu})
\leq
e^{-\lambda(1+\delta)\mu}\mathbb E[e^{\lambda S_n}]
\end{align*}
follows from $e^{\lambda S_n} \geq e^{\lambda(1+\delta)\mu}\mathbb{1}_{\{e^{\lambda S_n} \geq e^{\lambda(1+\delta)\mu}\}}$ and taking expectations. Using the exponential moment bound from the previous step gives
\begin{align*}
\mathbb P(S_n \geq (1+\delta)\mu)\leq\exp\{-\lambda(1+\delta)\mu+\mu(e^\lambda-1)\}.
\end{align*}
Substituting $\lambda=\log(1+\delta)$ and $e^\lambda-1=\delta$ gives
\begin{align*}
\mathbb P(S_n \geq (1+\delta)\mu)\leq\exp\{-\mu(1+\delta)\log(1+\delta)+\mu\delta\}.
\end{align*}
Equivalently,
\begin{align*}
\mathbb P(S_n \geq (1+\delta)\mu)\leq\left(\frac{e^\delta}{(1+\delta)^{1+\delta}}\right)^\mu.
\end{align*}
[guided]
The upper tail asks for the probability that $S_n$ is at least $(1+\delta)\mu$. The exponential method turns this comparison into a comparison of positive random variables, because exponentials preserve inequalities when the exponent parameter is positive.
Fix $\delta > 0$ and define $\lambda := \log(1+\delta)$. Then $\lambda > 0$, so the function
\begin{align*}
t \mapsto e^{\lambda t}
\end{align*}
is increasing on $\mathbb{R}$. Hence, whenever $S_n \geq (1+\delta)\mu$, we also have
\begin{align*}
e^{\lambda S_n} \geq e^{\lambda(1+\delta)\mu}.
\end{align*}
Therefore
\begin{align*}
\{S_n \geq (1+\delta)\mu\}
\subset
\{e^{\lambda S_n} \geq e^{\lambda(1+\delta)\mu}\}.
\end{align*}
Now we bound the probability of the exponential event. For every $\omega \in \Omega$,
\begin{align*}
e^{\lambda S_n(\omega)}
\geq
e^{\lambda(1+\delta)\mu}
\mathbb{1}_{\{e^{\lambda S_n} \geq e^{\lambda(1+\delta)\mu}\}}(\omega).
\end{align*}
Taking expectations with respect to $\mathbb P$ gives
\begin{align*}
\mathbb E[e^{\lambda S_n}]
\geq
e^{\lambda(1+\delta)\mu}
\mathbb P(e^{\lambda S_n} \geq e^{\lambda(1+\delta)\mu}),
\end{align*}
and therefore
\begin{align*}
\mathbb P(e^{\lambda S_n} \geq e^{\lambda(1+\delta)\mu})
\leq
e^{-\lambda(1+\delta)\mu}\mathbb E[e^{\lambda S_n}].
\end{align*}
The previous step computed and bounded the exponential moment:
\begin{align*}
\mathbb E[e^{\lambda S_n}]
\leq
\exp\{\mu(e^\lambda-1)\}.
\end{align*}
Substituting this estimate gives
\begin{align*}
\mathbb P(S_n \geq (1+\delta)\mu)
&\leq
\exp\{-\lambda(1+\delta)\mu+\mu(e^\lambda-1)\}.
\end{align*}
The choice $\lambda=\log(1+\delta)$ was made so that $e^\lambda-1=\delta$. Thus
\begin{align*}
\mathbb P(S_n \geq (1+\delta)\mu)\leq\exp\{-\mu(1+\delta)\log(1+\delta)+\mu\delta\}.
\end{align*}
Equivalently,
\begin{align*}
\mathbb P(S_n \geq (1+\delta)\mu)\leq\left(\frac{e^\delta}{(1+\delta)^{1+\delta}}\right)^\mu.
\end{align*}
[/guided]
[/step]
[step:Choose $\lambda=\log(1-\delta)$ to prove the lower-tail bound]
Fix $\delta \in (0,1)$ and define $\lambda := \log(1-\delta)$. Then $\lambda < 0$ and $e^\lambda=1-\delta$. Since the map $t \mapsto e^{\lambda t}$ is decreasing on $\mathbb{R}$,
\begin{align*}
\{S_n \leq (1-\delta)\mu\}
\subset
\{e^{\lambda S_n} \geq e^{\lambda(1-\delta)\mu}\}.
\end{align*}
Using the same non-negative random variable estimate as above,
\begin{align*}
\mathbb P(S_n \leq (1-\delta)\mu)\leq e^{-\lambda(1-\delta)\mu}\mathbb E[e^{\lambda S_n}].
\end{align*}
Using the exponential moment bound gives
\begin{align*}
\mathbb P(S_n \leq (1-\delta)\mu)\leq\exp\{-\lambda(1-\delta)\mu+\mu(e^\lambda-1)\}.
\end{align*}
Substituting $\lambda=\log(1-\delta)$ and $e^\lambda-1=-\delta$ yields
\begin{align*}
\mathbb P(S_n \leq (1-\delta)\mu)\leq\exp\{-\mu(1-\delta)\log(1-\delta)-\mu\delta\}.
\end{align*}
Equivalently,
\begin{align*}
\mathbb P(S_n \leq (1-\delta)\mu)\leq\left(\frac{e^{-\delta}}{(1-\delta)^{1-\delta}}\right)^\mu.
\end{align*}
[/step]
[step:Prove the logarithmic inequalities that imply the quadratic bounds]
Define
Let $\phi_+: [0,1] \to \mathbb{R}$ be the function defined by
\begin{align*}
\phi_+(t)=(1+t)\log(1+t)-t-\frac{t^2}{3}.
\end{align*}
Then
\begin{align*}
\phi_+'(t)=\log(1+t)-\frac{2t}{3},
\qquad
\phi_+''(t)=\frac{1}{1+t}-\frac{2}{3}
=
\frac{1-2t}{3(1+t)}.
\end{align*}
Thus $\phi_+''(t)\geq 0$ on $[0,1/2]$ and $\phi_+''(t)\leq 0$ on $[1/2,1]$. Since $\phi_+'(0)=0$ and
\begin{align*}
\phi_+'(1)=\log 2-\frac{2}{3}>0,
\end{align*}
the derivative $\phi_+'$ increases on $[0,1/2]$ and then decreases on $[1/2,1]$ while remaining non-negative. Hence $\phi_+$ is non-decreasing on $[0,1]$, and $\phi_+(0)=0$ gives
\begin{align*}
(1+\delta)\log(1+\delta)-\delta \geq \frac{\delta^2}{3}
\end{align*}
for every $\delta \in (0,1)$.
Next define
Let $\phi_-: [0,1) \to \mathbb{R}$ be the function defined by
\begin{align*}
\phi_-(t)=t+(1-t)\log(1-t)-\frac{t^2}{2}.
\end{align*}
Then
\begin{align*}
\phi_-'(t)
=
-\log(1-t)-t,
\qquad
\phi_-''(t)
=
\frac{1}{1-t}-1
=
\frac{t}{1-t}
\geq 0.
\end{align*}
Since $\phi_-'(0)=0$, it follows that $\phi_-'(t)\geq 0$ for $t \in [0,1)$, and hence $\phi_-$ is non-decreasing on $[0,1)$. Since $\phi_-(0)=0$,
\begin{align*}
\delta+(1-\delta)\log(1-\delta)\geq \frac{\delta^2}{2}
\end{align*}
for every $\delta \in (0,1)$.
[/step]
[step:Insert the logarithmic inequalities into the multiplicative bounds]
Let $\delta \in (0,1)$. The upper-tail multiplicative estimate can be written as
\begin{align*}
\mathbb P(S_n \geq (1+\delta)\mu)
\leq
\exp\{-\mu((1+\delta)\log(1+\delta)-\delta)\}.
\end{align*}
Using
\begin{align*}
(1+\delta)\log(1+\delta)-\delta \geq \frac{\delta^2}{3}
\end{align*}
gives
\begin{align*}
\mathbb P(S_n \geq (1+\delta)\mu)
\leq
\exp\left\{-\frac{\mu\delta^2}{3}\right\}.
\end{align*}
Similarly, the lower-tail multiplicative estimate can be written as
\begin{align*}
\mathbb P(S_n \leq (1-\delta)\mu)
\leq
\exp\{-\mu(\delta+(1-\delta)\log(1-\delta))\}.
\end{align*}
Using
\begin{align*}
\delta+(1-\delta)\log(1-\delta)\geq \frac{\delta^2}{2}
\end{align*}
gives
\begin{align*}
\mathbb P(S_n \leq (1-\delta)\mu)
\leq
\exp\left\{-\frac{\mu\delta^2}{2}\right\}.
\end{align*}
This proves all four asserted estimates.
[/step]
