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!

Solution 1:

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.