Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

How should one go about proving the following with induction?

$$ \left| \bigcup_{i \in I} A_i \right| = \sum_{J \subseteq I} (-1)^{|J|+1} \left|\bigcap_{i \in J} A_i \right| $$

I is just a finite set, and $A_i$ is just any set within it.

share|improve this question
    
Have you decided what the induction variable should be? –  Trevor Wilson Feb 12 '13 at 20:28
    
the size of I, ie. number of sets stored in I –  user60862 Feb 12 '13 at 20:48
    
How is this formula called again? I only know its name in my mother tongue. –  1015 Feb 12 '13 at 21:11
    
Cardinality of set union –  user60862 Feb 12 '13 at 21:30
1  
@julien: Inclusion-exclusion. –  Asaf Karagila Feb 12 '13 at 23:06
show 1 more comment

2 Answers 2

The formula is slightly incorrect: it’s important to require that the sets $J$ appearing in the summation be non-empty, so the formula should read

$$\left| \bigcup_{i \in I} A_i \right| = \sum_{\varnothing\ne J \subseteq I} (-1)^{|J|+1} \left|\bigcap_{i \in J} A_i \right|\;.\tag{1}$$

For a proof by induction on $|I|$, start with the trivial verification that $(1)$ holds when $|I|=1$. Then assume that it holds for $|I|=n$ for some $n\ge 1$, let $\mathscr{A}=\{A_i:i\in I\}$ be a family of $n+1$ sets, and show that $(1)$ holds for $\mathscr{A}$. The natural way to approach this is to fix some $i_0\in I$ and let $I_0=I\setminus\{i_0\}$, so that $|I_0|=n$, and you can apply the induction hypothesis to $\{A_i:i\in I_0\}$. You’ll have

$$\left|\bigcup_{i\in I}A_i\right|=\left|A_{i_0}\cup\bigcup_{i\in I_0}A_i\right|\;,\tag{2}$$

and you know from the induction hypothesis that $$\left| \bigcup_{i \in I_0} A_i \right| = \sum_{\varnothing\ne J \subseteq I_0} (-1)^{|J|+1} \left|\bigcap_{i \in J} A_i \right|\;.$$

If you knew that the $|I|=2$ case of $(1)$ was true, you could apply it to $(2)$ to get

$$\begin{align*} \left|\bigcup_{i\in I}A_i\right|&=|A_{i_0}|+\left| \bigcup_{i \in I_0} A_i \right|-\left|A_{i_0}\cap\bigcup_{i \in I_0} A_i \right|\\\\ &=|A_{i_0}|+\left| \bigcup_{i \in I_0} A_i \right|-\left|\bigcup_{i\in I_0}(A_{i_0}\cap A_i)\right|\;, \end{align*}\tag{3}$$

and you can now apply the induction hypothesis to each of the last two terms, since $|I_0|=n$. You’ll still have a little work to do to combine the sums and see that you really do get $$\sum_{\varnothing\ne J \subseteq I} (-1)^{|J|+1} \left|\bigcap_{i \in J} A_i \right|\;,$$ and of course you still have to prove that $(1)$ holds when $|I|=2$ in order to use that to get $(3)$.


It’s entirely possible to prove $(1)$ without using induction. Indeed, one can give a rather shorter proof. I’ve included one below, spoiler-protected; mouse-over to see it.

For each $x\in\bigcup_{i\in I}A_i$ let $I(x)=\{i\in I:x\in A_i\}$. For each $J\subseteq I$ and $x\in\bigcup_{i\in I}A_i$, $x\in\bigcap_{i\in J}A_i$ if and only if $J\subseteq I(x)$. Thus, the contribution of $x$ to the sum on the righthand side of $(1)$ is $+1$ for each non-empty $J\subseteq I(x)$ such that $|J|$ is odd, and $-1$ for each non-empty $J\subseteq I(x)$ such that $|J|$ is even. Let $n(x)=|I(x)|$, the number of sets in the collection $\{A_i:i\in I\}$ containing $x$. It’s well-known (and proved a number of times on this site) that exactly half of the $2^{n(x)}$ subsets of $I(x)$ have even cardinality. The empty set has even cardinality, so if we exclude it, $I(x)$ has $2^{n(x)-1}$ subsets of odd cardinality and $2^{n(x)-1}-1$ subsets of even cardinality. Thus, each $x\in\bigcup_{i\in I}A_i$ contributes a total of $2^{n(x)-1}(1)+\left(2^{n(x)-1}-1\right)(-1)=1$ to the sum in $(1)$, which therefore must be $\left|\bigcup_{i\in I}A_i\right|$.

share|improve this answer
add comment

First prove the result for $\# \mathrm I = 2$. Then do the induction by splitting like this $$ \# (\cup_{i = 1}^n \mathrm A_i\cup \mathrm A_{n+1})$$

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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