# Inequality with Binomial distribution

Let $n$ and $1\leq k \leq n$ be natural numbers. Prove the inequality $$\sum_{i=k}^n \binom{n}{i}\bigg(\frac{k}{n+1}\bigg)^i\bigg(1-\frac{k}{n+1}\bigg)^{n-i} \leq 1 - \frac{1}{e}$$

Equivalently, if $X\sim$ Bin($n$,$\frac{k}{n+1}$), prove that $\mathbb{P}[X\geq k] \leq 1 - \frac{1}{e}$.

My attempt: It may be helpful to show that the LHS tends to $1-\frac{1}{e}$ as $n \to \infty$ (already did that) and that the LHS is an increasing function on $n$ (have not done that).

• I don't think @gimusi's argument is correct. – DesmondMiles Mar 30 '18 at 17:40
• did you verify after my new comments? – gimusi Apr 1 '18 at 8:47

HINT

Note that

$$\sum_{i=k}^n \binom{n}{i}\bigg(\frac{k}{n+1}\bigg)^i\bigg(1-\frac{k}{n+1}\bigg)^{n-i} =\sum_{i=0}^n \binom{n}{i}\bigg(\frac{k}{n+1}\bigg)^i\bigg(1-\frac{k}{n+1}\bigg)^{n-i} -\sum_{i=0}^{k-1} \binom{n}{i}\bigg(\frac{k}{n+1}\bigg)^i\bigg(1-\frac{k}{n+1}\bigg)^{n-i}=1^n-\sum_{i=0}^{k-1} \binom{n}{i}\bigg(\frac{k}{n+1}\bigg)^i\bigg(1-\frac{k}{n+1}\bigg)^{n-i}$$

and show that

$$\sum_{i=0}^{k-1} \binom{n}{i}\bigg(\frac{k}{n+1}\bigg)^i\bigg(1-\frac{k}{n+1}\bigg)^{n-i}\stackrel{k=1}\ge \sum_{i=0}^0 \binom{n}{i}\bigg(\frac{1}{n+1}\bigg)^i\bigg(1-\frac{1}{n+1}\bigg)^{n-i}=\bigg(1-\frac{1}{n+1}\bigg)^{n}\ge\frac 1e$$

• Sorry, but how did you get from $sum_{i=0}^1$ (things) to n/(n+1)*(1-1/(n+1))^{n-1}; i.e. how did k dissapear magically and became 1? – DesmondMiles Mar 30 '18 at 14:05
• @DesmondMiles sorry there is a typo k ia assumed $=1$, I check and fix this point – gimusi Mar 30 '18 at 14:06
• @DesmondMiles I've made also a stupid mistake with the sum index. Now it should be ok and also simpler! – gimusi Mar 30 '18 at 14:12
• Thank you but how exactly do we show the inequality with (k=1) written above it? Apologies if I am not seeing something stupid. The gap in my attempt is quite similar. – DesmondMiles Mar 30 '18 at 14:21
• @DesmondMiles Because it is a sum of positive terms thus the minimum is attained fro k=1, and the quantity obtained is bounded below by $1/e$. – gimusi Mar 30 '18 at 14:24