I am reading a paper and found the following Lemma without a proof.
Let $X_1, \ldots, X_{n+1}$ be independent Bernoulli random variables, where $\Pr[X_i = 1] = p$. Let $E$ be the event that the first $n$ variables are all $1$, but the $X_{n+1}$ is $0$. Then $\Pr[E] \leq \frac{1}{en}$.
I understand that $\Pr[E] = p^n(1-p)$. How is it that $p^n(1-p) \leq \frac{1}{en}$?
Using the AM-GM for first inequality below, we have $$ p^n(1-p)=n^n\left[(p/n)^n(1-p)\right]\leq n^n\left(\frac{1}{n+1}\right)^{n+1}=\frac{1}n\left(1-\frac{1}{n+1}\right)^{n+1}<\frac{1}{ne}. $$ The second inequality uses the fact that $a_n=(1-1/n)^n$ increases in $n$ and converges to $1/e$ as $n\to\infty$.
Maximize the function $f(p) = p^n (1-p)$. The maximum is at $p = p_0 = n/(n+1)$, where $$f(p_0) = \dfrac{n^n}{(n+1)^{n+1}}$$ The statement that $f(p_0) \le 1/(en)$ is equivalent (after taking logarithms) to $$ \ln \left( 1 + \dfrac{1}{n}\right) \ge \dfrac{1}{n+1} \ \text{for}\ n \ge 1$$ With $n = 1/t$, this becomes $$ \ln(1 + t) \ge \dfrac{t}{1+t} = 1 - \dfrac{1}{1+t} $$ which is actually true for all $t \ge 0$. Note that both sides are equal for $t = 0$, and the derivatives $$ \dfrac{1}{1+t} \ge \dfrac{1}{(1+t)^2}\ \text{for}\ t \ge 0$$
