Bound on probability of independent events

Question

I found this problem which I'm struggling with. Any help with it is appreciated.

Let $E = \{E_1, \ldots E_k \}$ be some set of events in a probability space, and let $p = \sum \Pr(E_i)$. Fixing $n \leq k$ we set $P_n$ to be the event that some $n$ independent events from $E$ happen. The problem is to bound the probability of $P_n$ as $\Pr(P_n) \leq p^n / n!$

Thanks

Answer 1

Event $P_n=\cup_{\{i_1,i_2,...i_n\}\subset \{1,...,k\},\text{Events }E_{i_1},E_{i_2},...E_{i_n}\text{ are independent}}\cap_j{E_{i_j}}$

$\text{Pr}(P_n)\le \sum_{\{i_1,i_2,...i_n\}\subset \{1,...,k\},\text{Events }E_{i_1},E_{i_2},...E_{i_n}\text{ are independent}}\prod_j{\text{Pr}(E_{i_j})}$

Expanding the summation to all sets of $n$ events, not necessarily independent,

$\text{Pr}(P_n)\le \sum_{\{i_1,i_2,...i_n\}\subset \{1,...,k\},\ j_1 \neq j_2 \implies i_{j_1} \neq i_{j_2}}\prod_j{\text{Pr}(E_{i_j})}$.

But each summand on the right appears $n!$ times in $(\sum_{i=1}^{k}{\text{Pr}(E_i)})^n=p^n$ along with other nonnegative terms. So

$\text{Pr}(P_n)\le p^n/n!\quad$.