Prove that for all $k \in \mathbb{N}^*$, $\mathbb{P}(S \ge k) \le \dfrac{1}{2^n}\left(\dfrac{en}{k}\right)^k$

Question

Problem: Let $b$ be a random variable such that $\mathbb{P}(b=0) = \mathbb{P}(b=1) = \dfrac{1}{2}$. Let $b_1,\ldots,b_n$ be independent copies of $b$ and $S = \sum_{i=1}^n b_i$. Prove that $$\forall k \in \mathbb{N}^*, \mathbb{P}(S \ge k) \le \dfrac{1}{2^n}\left(\dfrac{en}{k}\right)^k.$$

My attempt: Since $b_i$ are i.i.d variables then \begin{align*} \mathbb{E}\left[e^{\lambda S}\right] & = \mathbb{E}\left[e^{\lambda (b_1 + b_2 + \ldots + b_n)}\right] \\ & = \mathbb{E}\left[\prod_{i=1}^n e^{\lambda b_i}\right] = \prod_{i=1}^n \mathbb{E}\left[e^{\lambda b_i}\right]\\ & = \left(\mathbb{E}\left[e^{\lambda b}\right]\right)^n \tag{1.1} \end{align*} Moreover, since $b \sim \text{Ber}(1/2)$ then \begin{align*} \mathbb{E}\left[e^{\lambda b}\right] &= \mathbb{P}(b=0)\cdot e^{\lambda \cdot 0} + \mathbb{P}(b=1)\cdot e^{\lambda \cdot 1}\\ & = \dfrac{1}{2} + \dfrac{1}{2} e^{\lambda} = \dfrac{1}{2}(1+e^{\lambda}) \tag{1.2} \end{align*} From (1.1) and (1.2), we obtain that \begin{align*} \mathbb{E}\left[e^{\lambda S}\right] & = \dfrac{1}{2^n} (1+e^{\lambda})^n = \dfrac{1}{2^n} \exp\left(n \ln(1+e^\lambda)\right)\\ & = \dfrac{1}{2^n} \exp\left(n\left(e^\lambda - \dfrac{e^{2\lambda}}{2}\right)\right) \tag{Taylor's expansion of $\ln(1+x)$}\\ & \le \dfrac{1}{2^n}\exp(ne^\lambda) \tag{QED} \end{align*} Hence, by using Markov's inequality, we have for any $k \in \mathbb{N}^*$ that \begin{align*} \mathbb{P}(S \ge k) &\le \dfrac{\mathbb{E}\left[e^{\lambda S}\right]}{e^{\lambda k}}\\ & \le \dfrac{1}{2^n}\dfrac{\exp(ne^\lambda)}{e^{\lambda k}} \end{align*}

Now, I am stuck here. I hope anyone can give me some hints to deal with the problem.

Answer 1

For $k>n$ LHS is $0$ and there is nothing to prove (as observed by you) . Actually, the stated inequality can be false for $k\le n$. For a counter-example take $k=1$. Then $P(S\ge k)=1-P(S=0)=1-\frac 1 {2^{n}}$ and the inequality becomes $1-\frac 1 {2^{n}} \le \frac {en} {2^{n}}$ or $2^{n}-1\le en$ This is clearly false for large $n$.

Answer 2

Correction: As @geetha290krm pointed out, the statement is actually wrong. In fact, $$ \frac{1}{2^n} \sum_{k' \geq k} \binom{n}{k'} = \frac{1}{2^n} \sum_{k' \geq k} \binom{n}{n - k'} = \frac{1}{2^n} \sum_{k' \leq n - k} \binom{n}{n - k'} \leq \frac{1}{2^n} (\frac{en}{n - k})^{n - k}. $$

---

Original answer (which is wrong): Another possible way is to directly use $$\Pr[S \geq k] = \sum_{k' \geq k} \Pr[S = k] = \frac{1}{2^n} \sum_{k' \geq k} \binom{n}{k'}.$$ Then you can use the bound of the partial sum of binomial coefficients (See, e.g., How to prove upper bound for partial sum of binomial coefficients) to get $$\frac{1}{2^n} \sum_{k' \geq k} \binom{n}{k'} \leq \frac{1}{2^n} (\frac{en}{k})^k.$$