The Poincare's inclusion exclusion formula is given by
\begin{align} \Bbb{I}_{\bigcup_{1\leq j\leq n}A_j}=\sum_{1\leq j\leq n}\Bbb{I}_{A_j}+\sum^{n}_{r=2}(-1)^{r+1}\sum_{1\leq i_1
where $\Bbb{I}$ represents the indicator function. I want to prove this formula by induction. Below is my work
MY TRIAL
Assume true for $n,$ that is for $P_{n}$
\begin{align} \Bbb{I}_{\bigcup_{1\leq j\leq n}A_j}=\sum_{1\leq j\leq n}\Bbb{I}_{A_j}+\sum^{n}_{r=2}(-1)^{r+1}\sum_{1\leq i_1
Now \begin{align} \bigcup_{1\leq j\leq n+1}A_j=\left(\bigcup_{1\leq j\leq n}A_j\right)\cup A_{n+1}\end{align}
Applying the indicator function rule,
\begin{align} \Bbb{I}_{\bigcup_{1\leq j\leq n+1}A_j}=\Bbb{I}_{\bigcup_{1\leq j\leq n}A_{n}}+\Bbb{I}_{A_{n+1}}-\Bbb{I}_{\bigcup_{1\leq j\leq n}A_{n}}\Bbb{I}_{A_{n+1}}\end{align}
So, we apply $P_n$ to get
\begin{align} \Bbb{I}_{\bigcup_{1\leq j\leq n+1}A_j}=&\sum_{1\leq j\leq n}\Bbb{I}_{A_j}+\sum^{n}_{r=2}(-1)^{r+1}\sum_{1\leq i_1
\end{align}
Again, applying $P_{n}$, to the last term, we get
\begin{align} \Bbb{I}_{\bigcup_{1\leq j\leq n+1}A_j}=&\sum_{1\leq j\leq n+1}\Bbb{I}_{A_j}+\sum^{n}_{r=2}(-1)^{r+1}\sum_{1\leq i_1
From here, I'm not sure how to continue. Any help please? Thanks!
Answer
At your last line observe that
$$\Bbb{I}_{A_j}\Bbb{I}_{A_{n+1}}
=\Bbb{I}_{A_{j}\cap A_{n+1}}$$
and
$$\Bbb{I}_{A_{i_1}\cap A_{i_2}\cap \cdots\cap A_{i_r} }\Bbb{I}_{A_{n+1}}
=\Bbb{I}_{A_{i_1}\cap A_{i_2}\cap \cdots\cap A_{i_r}\cap A_{n+1}}.$$
These terms provide the indicator functions of the multiple intersections
of the $A_i$ that involve $A_{n+1}$.
No comments:
Post a Comment