Let $A_1,A_{2,\dots ,}{A}_n$be events, and let $N$denote the number of them that occur. Also, let $I=1$if all of these events occur, and let it be $0$otherwise. Prove Bonferroni’s inequality, namely,

$P(A_1\cdots A_n)\ge \sum _{i=1}^{n}P\left(A_i\right)-(n-1)$

Hint: Argue first thatlocalid="1648086485785" $N\le n-1+I$

Let A$1$,A$2$,...,An be events, and let N denote the number of them that occur.

Given the values as follow,

$P(A_1\cdots A_n)\ge \sum _{i=1}^{n}P\left(A_i\right)-(n-1)$

N$\le$ n − 1 + $1$.

$\text{Let}N\text{represents the number of events}{A}_1,A_2,\dots ,A_n\text{that occur and let indicator variable}I\text{be defined as:}$

localid="1648086527186" $I=\left\{\begin{array}{l}1,\text{if}{A}_1{A}_2\cdots A_n\text{occurs}\\ 0,\text{if}{A}_1{A}_2\cdots A_n\text{does not occur}\end{array}\right.$

$\text{Further, if indicator variables}{I}_j,j=1,2,\dots ,n\text{, are defined as:}$

localid="1648086533299" $I_j=\left\{\begin{array}{l}1,\text{if}{A}_j\text{occurs}\\ 0,\text{if}{A}_j\text{does not occur}\end{array}\right.$

Then,

$N=\sum _{j=1}^n{I}_j$

If all of the events $A_i,i=1,2,\dots ,n$occur, then$N=nandI=1$

and in that case, variable $N$can be represented as

$N=n-1+1=n-1+I$

On the other hand, if all of the events $A_i,i=1,2,\dots ,n$do not occur, then

$N<n\text{and}I=0$

and in that case

$N\le n-1+0=n-1+I.$

$\text{Hence,}N\le n-1+I$

Now, use induction to prove Bonferroni's inequality.

The first case is $n=1$, which is the trivial statement, since

$P\left(A_1\right)=P\left(A_1\right)$

Let's take the second case.

In second case it is $n=2$since $1\ge P\left(A_1\cup A_2\right)=P\left(A_1\right)+P\left(A_2\right)-P\left(A_1{A}_2\right)$.

Here, we have $P\left(A_1{A}_2\right)\ge P\left(A_1\right)+P\left(A_2\right)-1$

Therefore, the statement is true.

From the above steps, we obtain that, for events $A_1,A_2,\dots ,A_n$, we have

$P\left(A_1\cdots A_n\right)\ge \sum _{i=1}^n P\left(A_i\right)-(n-1)$

Let's prove the desired statement for $n+1$.

Therefore, consider the events$A_1,A_2,\dots ,A_n,A_{n+1}$. Because$A_1,A_2,\dots ,A_{n-1},A_n\cap A_{n+1}$is a list of$n$events.

$P\left(A_1{A}_2\cdots A_n{A}_{n+1}\right)=P\left(A_1\cap \cdots A_{n-1}\cap A_n\cap A_{n+1}\right)$$=P{\left(A_1{A}_2\cdots A_{n-1}\left(A_n\cap A_{n+1}\right)\right)}^{\text{inductive hypothesis}}\ge P\left(A_1\right)+\cdots +P\left(A_{n-1}\right)+P\left(A_n\cap A_{n+1}\right)-(n-1)$

But, since the statement is true for $n=2$, we have that:

$P\left(A_n\cap A_{n+1}\right)\ge P\left(A_n\right)+P\left(A_{n+1}\right)-1$

Therefore, we can concluded that

$P\left(A_1{A}_2\cdots A_n{A}_{n+1}\right)\ge P\left(A_1\right)+\cdots +P\left(A_{n-1}\right)+\left[P\left(A_n\right)+P\left(A_{n+1}\right)-1\right]-(n-1)$

$=P\left(A_1\right)+\cdots +P\left(A_{n-1}\right)+P\left(A_n\right)+P\left(A_{n+1}\right)-n$

$=P\left(A_1\right)+\cdots +P\left(A_{n-1}\right)+P\left(A_n\right)+P\left(A_{n+1}\right)-\left(\right(n+1)-1)$

If all of the events $A_i,i=1,2,\dots ,n$occur, then

$N=n$ and $I=1$,

while on the other side, if all of the events $A_i,i=1,2,\dots ,n$do not occur, then

$N<n\text{and}I=0$

Therefore,$N\le n-1+I$