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).

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


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$$

  • $\begingroup$ 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? $\endgroup$ – DesmondMiles Mar 30 '18 at 14:05
  • $\begingroup$ @DesmondMiles sorry there is a typo k ia assumed $=1$, I check and fix this point $\endgroup$ – gimusi Mar 30 '18 at 14:06
  • $\begingroup$ @DesmondMiles I've made also a stupid mistake with the sum index. Now it should be ok and also simpler! $\endgroup$ – gimusi Mar 30 '18 at 14:12
  • $\begingroup$ 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. $\endgroup$ – DesmondMiles Mar 30 '18 at 14:21
  • $\begingroup$ @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$. $\endgroup$ – gimusi Mar 30 '18 at 14:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.