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

-
It's better to write explicitly the inequality here. – Patrick Li Oct 7 '12 at 14:38
I've added the description. – LittleSweet Oct 7 '12 at 15:07
isn't this inclusion exclusion principle? For odd number of terms you overcount the probability, for even number of terms you undercount. – cactus314 Oct 7 '12 at 15:24

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