# How to prove Bonferroni inequalities?

Define $$S_1 = \sum_{i=1}^n P(A_i)$$
and
$$S_2 =\sum_{1 \le i < j \le n}^n P(A_i \cap A_j)$$
as well as
$$S_k =\sum_{1 \le i_1 < \cdots < i_k \le n}^n P(A_{i_1} \cap \cdots \cap A_{i_k})$$
Then for odd $k$ in $\{1,\ldots,n\}$
$$P\left(\bigcup_{i=1}^n A_i\right) \le \sum_{j=1}^{k}(-1)^{j-1} S_j$$
For even $k$ in $\{2,\ldots,n\}$
$$P\left(\bigcup_{i=1}^n A_i\right) \ge \sum_{j=1}^{k}(-1)^{j-1}S_j$$

More details of Bonferroni inequalities or Boole’s inequality is here.

#### Solutions Collecting From Web of "How to prove Bonferroni inequalities?"

A proof is there. The main idea is that this is the integrated version of analogous pointwise inequalities and that, for every $k$,
$$S_k=\mathbb E\left({T\choose k}\right),\qquad T=\sum_{i=1}^n\mathbf 1_{A_i}.$$
Hence the result follows from the stronger inequalities asserting that, for every positive integer $N$,
$$\sum_{i=0}^k(-1)^ia_i,\qquad a_i={N\choose i},$$
is nonnegative when $k$ is even and nonpositive when $k$ is odd. In turn, this fact follows from the properties that the sequence $(a_i)_{0\leqslant i\leqslant N}$ is unimodal and that $\sum\limits_{i=0}^N(-1)^ia_i=0$.