Proof of Poincare's Inclusion-Exclusion Indicator Function Formula by Induction

Question

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<i_2<\cdots<i_r\leq n}\Bbb{I}_{A_{i_1}\cap A_{i_2}\cap \cdots\cap A_{i_r} }\end{align} 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<i_2<\cdots<i_r\leq n}\Bbb{I}_{A_{i_1}\cap A_{i_2}\cap \cdots\cap A_{i_r} }\end{align} 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<i_2<\cdots<i_r\leq n}\Bbb{I}_{A_{i_1}\cap A_{i_2}\cap \cdots\cap A_{i_r} }\\&+\Bbb{I}_{A_{n+1}}-\Bbb{I}_{\bigcup_{1\leq j\leq n}A_{n}}\Bbb{I}_{A_{n+1}} \\=&\sum_{1\leq j\leq n+1}\Bbb{I}_{A_j}+\sum^{n}_{r=2}(-1)^{r+1}\sum_{1\leq i_1<i_2<\cdots<i_r\leq n}\Bbb{I}_{A_{i_1}\cap A_{i_2}\cap \cdots\cap A_{i_r} }\\&-\Bbb{I}_{\bigcup_{1\leq j\leq n}A_{n}}\Bbb{I}_{A_{n+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<i_2<\cdots<i_r\leq n}\Bbb{I}_{A_{i_1}\cap A_{i_2}\cap \cdots\cap A_{i_r} }\\&-\left(\sum_{1\leq j\leq n}\Bbb{I}_{A_j}+\sum^{n}_{r=2}(-1)^{r+1}\sum_{1\leq i_1<i_2<\cdots<i_r\leq n}\Bbb{I}_{A_{i_1}\cap A_{i_2}\cap \cdots\cap A_{i_r} }\right)\Bbb{I}_{A_{n+1}} \\=&\sum_{1\leq j\leq n+1}\Bbb{I}_{A_j}+\sum^{n}_{r=2}(-1)^{r+1}\sum_{1\leq i_1<i_2<\cdots<i_r\leq n}\Bbb{I}_{A_{i_1}\cap A_{i_2}\cap \cdots\cap A_{i_r} }\\&-\sum_{1\leq j\leq n}\Bbb{I}_{A_j}\Bbb{I}_{A_{n+1}}+\sum^{n}_{r=2}(-1)^{r+1}\sum_{1\leq i_1<i_2<\cdots<i_r\leq n}\Bbb{I}_{A_{i_1}\cap A_{i_2}\cap \cdots\cap A_{i_r} }\Bbb{I}_{A_{n+1}} \end{align} From here, I'm not sure how to continue. Any help please? Thanks!

Answer 1

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