Exclusion Inclusion Principle Induction Proof I got new home work that I was asked to proof the exclusion inclusion principle with induction,
and my question is how can I do that?
Any help will be appreciated!
 A: A big hint is to prove the result for three sets, $A_1, A_2, A_3$, given the result for two sets. I assume you have already seen the result for two sets:
$$
|A_1\cup A_2| = |A_1|+|A_2|-|A_1\cap A_2|
$$
So what do we get with three sets? We start by writing the three-fold union as the union of two sets:
$$
|A_1\cup A_2\cup A_3|=|(A_1\cup A_2)\cup A_3|
$$
and so we can use the two-set result on $A_1\cup A_2$ and $A_3$, so
$$
|(A_1\cup A_2)\cup A_3|=|A_1\cup A_2| + |A_3|-|(A_1\cup A_2)\cap A_3|
$$
Now we can use the two-set result on $|A_1\cup A_2|$ to get
$$\begin{align}
|A_1\cup A_2\cup A_3|&=|A_1\cup A_2| + |A_3|-|(A_1\cup A_2)\cap A_3|\\
 &=|A_1|+|A_2|-|A_1\cap A_2|+ |A_3|-|(A_1\cup A_2)\cap A_3|\\
 &=|A_1|+|A_2|+ |A_3|-|A_1\cap A_2|-|(A_1\cup A_2)\cap A_3|
\end{align}$$
Now use the distributive property on the last term:
$$
|A_1\cup A_2\cup A_3|=|A_1|+|A_2|+ |A_3|-|A_1\cap A_2|-|(A_1\cap A_3)\cup (A_2\cap A_3)|
$$
and use the two-set property yet again on the last term, with sets $A_1\cap A_3$ and $A_2\cap A_3$ to get
$$\begin{align}
|(A_1\cap A_3)\cup (A_2\cap A_3)|&=|A_1\cap A_3|+|A_2\cap A_3|-|(A_1\cap A_3)\cap (A_2\cap A_3)|\\
&=|A_1\cap A_3|+|A_2\cap A_3|-|A_1\cap A_2\cap A_3|
\end{align}$$
Finally, we substitute this into our big expression (remembering that it was negated) to get
$$\begin{align}
|A_1\cup A_2\cup A_3|=&\phantom{-}|A_1|+|A_2|+ |A_3|\\
&-|A_1\cap A_2|-|A_1\cap A_3|-|A_2\cap A_3|\\
&+|A_1\cap A_2\cap A_3|
\end{align}$$
In other words, we have that the size of a three-set union can be computed by
$$
|A_1\cup A_2\cup A_3| = \sum_{1\le i\le 3}|A_i|-\sum_{1\le i < j\le 3}|A_i\cap A_j|+\sum_{1\le i < j < k\le 3}|A_i\cap A_j\cap A_k|
$$

Now the bad news is that after all this work you won't use this result in your induction proof. It's only a hint to guide you in getting through the inductive step. You do indeed induct on the number, $n$, of sets. The base case is $n=2$, which is just the known result we stated at the very top of this post.
The hard part is figuring out how to write the result in a tidy form. I'd suggest that you define the various summands using something like this:
$$
\text{Let }J_{n, k}=\sum_{1\le i_1<i_2<\cdots<i_k\le n}|A_{i_1}\cap A_{i_2}\cap\dots\cap A_{i_k}|
$$
so in the inductive step you want to show that if
$$
|A_1\cup A_2\cup\dots\cup A_n|=\sum_{k=1}^n(-1)^{k+1}J_{n, k}
$$
then
$$
|A_1\cup A_2\cup\dots\cup A_n\cup A_{n+1}|=\sum_{k=1}^{n+1}(-1)^{k+1}J_{n+1, k}
$$
To do this, adapt the hint I gave to show the inductive step and thus complete your proof. Best of luck.
