# Proof of Bonferroni Inequalities

###### Definitions and Notation.

A is a triple $(X,\Sigma,\mu)$, where $X$ is a set, $\Sigma$ is a $\sigma$-algebra over $X$, and $\mu\colon\Sigma\rightarrow[0,\infty]$ is a measure, that is, a non-negative function that is countably additive. If $A\in\Sigma$, the of $A$ is the function $\chi_{A}\colon X\rightarrow\mathbb{R}$ defined by $\chi_{A}(x)=1$ if $x\in A$, $\chi_{A}(x)=0$ if $x\notin A$. A unimodal sequence is a sequence of real numbers $a_{0},a_{1},\ldots,a_{n}$ for which there is an index $k$ such that $a_{i}\leq a_{i+1}$ for $i and $a_{i}\geq a_{i+1}$ for $i\geq k$.

The proof of the following easy lemma is left to the reader:

###### Lemma 1.

If $a_{0}\leq a_{1}\leq\ldots\leq a_{k}\geq a_{k+1}\geq a_{k+2}\geq\ldots\geq a_{n}$ is a unimodal sequence of non-negative real numbers with $\sum_{i=0}^{n}(-1)^{i}a_{i}=0$, then $\sum_{i=0}^{j}(-1)^{i}a_{i}\geq 0$ for even $j$ and $\leq 0$ for odd $j$.

Since the binomial sequence $(\binom{a}{i})_{0\leq i\leq n}$ with integer $a>0$ and integer $n\geq a$ satisfies the hypothesis of Lemma 1, we have:

###### Corollary 1.

If $a$ is a positive integer, $\sum_{i=0}^{j}(-1)^{i}\binom{a}{i}\geq 0$ for even $j$ and $\leq 0$ for odd $j$.

###### Lemma 2.

Let $(A_{i})_{1\leq i\leq n}$ be a sequence of sets and let $X=\bigcup_{1\leq i\leq n}A_{i}$. For $x\in X$, let $I(x)$ be the set of indices $j$ such that $x\in A_{j}$. If $1\leq k\leq n$,

 $\sum_{1\leq i_{1}

for all $x\in X$.

###### Proof.

$\chi_{A_{i_{1}}\cap A_{i_{2}}\cap\ldots\cap A_{i_{k}}}(x)=1$ if $\{i_{1},i_{2},\ldots,i_{k}\}\subseteq I(x)$, and $=0$ otherwise. Therefore the sum equals the number of $k$-subsets of $I(x)$, which is $\binom{|I(x)|}{k}$. ∎

###### Theorem 1.

Let $(X,\Sigma,\mu)$ be a measure space. If $(A_{i})_{1\leq i\leq n}$ is a finite sequence of measurable sets all having finite measure, and

 $S_{j}=\mu(A_{1}\cup A_{2}\cup\ldots\cup A_{n})+\sum_{k=1}^{j}(-1)^{k}\sum_{1% \leq i_{1}

then $S_{j}\geq 0$ for even $j$, and $\leq 0$ for odd $j$. Moreover, $S_{n}=0$ (Principle of Inclusion-Exclusion).

###### Proof.

Let $Y=\bigcup_{1\leq i\leq n}A_{i}$.

 $\displaystyle S_{j}$ $\displaystyle=$ $\displaystyle\int_{Y}d\mu+\sum_{k=1}^{j}(-1)^{k}\sum_{1\leq i_{1} $\displaystyle=$ $\displaystyle\int_{Y}d\mu+\sum_{k=1}^{j}(-1)^{k}\int_{Y}(\sum_{1\leq i_{1}

By Lemma 2,

 $\displaystyle S_{j}$ $\displaystyle=$ $\displaystyle\int_{Y}d\mu+\sum_{k=1}^{j}(-1)^{k}\int_{Y}\binom{|I(x)|}{k}d\mu$ $\displaystyle=$ $\displaystyle\sum_{k=0}^{j}(-1)^{k}\int_{Y}\binom{|I(x)|}{k}d\mu$ $\displaystyle=$ $\displaystyle\int_{Y}\sum_{k=0}^{j}(-1)^{k}\binom{|I(x)|}{k}d\mu$

Since $|I(x)|>0$ for $x\in Y$, it follows from Corollary 1 that, in the last integral, the integrand is $\geq 0$ for even $j$ and $\leq 0$ for odd $j$. Therefore the same is true for the integral itself. In addition, the integrand is identically 0 for $j=n$, hence $S_{n}=0$. ∎

This proof shows that at the heart of Bonferroni’s inequalities lie similar inequalities governing the binomial coefficients.

Title Proof of Bonferroni Inequalities ProofOfBonferroniInequalities 2013-03-22 19:12:44 2013-03-22 19:12:44 csguy (26054) csguy (26054) 6 csguy (26054) Proof msc 60A99