Bound on Binomial cumulative distribution

Question

Let $X$ be a binomial r.v. with parameters $n \in \mathbb{N}$ and $p \in [0,1]$, we write $X \sim B(n, p)$. The cumulative distribution function can be expressed as $$ \Pr(X\leq k) = \sum^k_{i=0} \binom{n}{i} p^{i} (1-p)^{n-i}. $$ I found in an article that $$ \Pr(X\leq k) \leq \binom{n}{k} (1-p)^{n-k}, $$ but I fail to see how this bound has been obtained.

Answer 1

You can think of $X$ as the number of successes out of $n$ independent events $E_1,E_2,\dots,E_n$, each with probability $p$ of success. We can write $$ \{X\le k\}=\bigcup_{\substack{S\subseteq \{1,\dots,n\} \\ |S|=n-k }} \bigcap_{i\in S} E_i^c $$ In words, the event $X\le k$ occurs if and only if there exists a subset of the $n$ events with cardinality $n-k$ such that none of the events in that subset occur. You then use the Union Bound to get $$ P(X\le k)\le \sum_{\substack{S\subseteq \{1,\dots,n\} \\ |S|=n-k }} P\left(\bigcap_{i\in S} E_i^c\right) $$ Conclude by noting that $P\left(\bigcap_{i\in S} E_i^c\right)=(1-p)^{n-k}$, as this is the probability of $n-k$ particular events failing, and there are $\binom{n}{n-k}=\binom nk$ summands.