7
$\begingroup$

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!

$\endgroup$
  • $\begingroup$ Why don't you start by writing what you have now? I'm sure you can do the base case (PS what are you inducting on, anyhow, the number of sets in the union?). Write down the induction hypothesis, write down what you try to attain from this hypothesis, and the fun can begin after that. $\endgroup$ – Evan Sep 6 '13 at 20:05
  • $\begingroup$ Thank you for the responding ,but I really don't know how to start... $\endgroup$ – Gil Sep 6 '13 at 20:13
  • 1
    $\begingroup$ You start by writing the full statement that you need to prove. Next you isolate the variable that you intend to do the induction. Then you write down the base case for $n=0$ or $n=1$, you continue by writing the complete statement for the induction hypothesis for $n$ and then you proceed to prove the case for $n+1$. It is often the case that we forget to write the statement that we want to prove, and then we don't know what we need to prove. Writing it down helps us understand it better, and sometimes it even simplifies everything to a purely technical (and sometimes simple too) manipulation. $\endgroup$ – Asaf Karagila Sep 6 '13 at 22:24
  • $\begingroup$ wikipedia brother. just ask wiki. he is a good friend of mine. yehey. im sorry :) $\endgroup$ – user156908 Jun 13 '14 at 13:18
21
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.