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 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 Pn
\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 ⋃1≤j≤n+1Aj=(⋃1≤j≤nAj)∪An+1
Applying the indicator function rule,
I⋃1≤j≤n+1Aj=I⋃1≤j≤nAn+IAn+1−I⋃1≤j≤nAnIAn+1
So, we apply Pn 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 Pn, 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
IAjIAn+1=IAj∩An+1
and
IAi1∩Ai2∩⋯∩AirIAn+1=IAi1∩Ai2∩⋯∩Air∩An+1.
These terms provide the indicator functions of the multiple intersections
of the Ai that involve An+1.
No comments:
Post a Comment