# Prove the general inclusion-exclusion rule via mathematical induction

"For any finite set A, N(A) denotes the number of elements in A."

Theorem 9.3.3 The Inclusion/Exclusion Rule for Two or Three Sets
If A, B, and C are any finite sets, then
$N(A ∪ B) = N(A) + N(B) − N(A ∩ B)$ and $N(A ∪ B ∪ C) = N(A) + N(B) + N(C) − N(A ∩ B) − N(A ∩ C) −N(B ∩ C) + N(A ∩ B ∩ C)$.

"It can be shown using mathematical induction (see exercise 48 at the end of this section) that formulas analogous to those of Theorem 9.3.3 hold for unions of any finite number of sets."

Source: Discrete Mathematics with Applications Susanna S. Epp

My attempt(edited)

For all natural numbers n, let the P(n) be the following property:
$N(A_1 ∪ A_2 ∪ \cdots ∪ A_n)$
$= ∑ \limits_{1≤ a_1 ≤ n} N(A_{a_1}) - ∑ \limits_{1≤ a_1 < a_2 ≤ n} N(A_{a_1} ∩ A_{a_2}) + ∑ \limits_{1≤ {a_1} < {a_2} < n} N(A_{a_1} ∩ A_{a_2} ∩ A_n) - \cdots + (-1)^n N(A_1 ∩ A_2 ∩ \cdots ∩ A_n)$

Show that P(1) is true

As for P(1)
$N(A_1)= N(A_1)$ by The Addition Rule ......a

By the way, $∑ \limits_{1≤ i <j ≤ 1} N(A_{a_1} ∩ A_{a_2}) = 0$ since $A_{a_2}=Ø$
So $N(A_1) = ∑ \limits_{1≤ i ≤ 1} N(A_{a_1})=N(A_1)$....b
By a, b, P(1) is true

Show that for all integers $l$ with 1≤l≤m, $\space if \space p(l) \space \text{is true, then}\space p(m+1)$ is true.

Inductive hypothesis is $N(A_1 ∪ A_2 ∪ \cdots ∪ A_l)$
$\space\space\space = ∑ \limits_{1 ≤ a_1 ≤ l} N(A_{a_1}) - ∑ \limits_{1≤{a_1}<{a_2}≤l} N(A_{a_1} ∩ A_{a_2}) + ∑ \limits_{1≤ {a_1} <{a_2}< {a_3} ≤ l} N(A_{a_1} ∩ A_{a_2} ∩ A_{a_3}) - \cdots + (-1)^{l+1} N(A_1 ∩ A_2 ∩ \cdots ∩ A_l)$
as an inductive hypothesis.

Then we must show the following p(m+1) is true.

$N(A_1 ∪ A_2 ∪ \cdots ∪ A_m ∪ A_{m+1})$
$\space\space\space = ∑ \limits_{1≤ a_1 ≤ m+1} N(A_{a_1}) - ∑ \limits_{1≤ a_1 < a_2 ≤ m+1} N(A_{a_1} ∩ A_{a_2}) + ∑ \limits_{1≤ a_1 < a_2 < a_3 ≤m+1} N(A_{a_1} ∩ A_{a_2} ∩ A_{a_3}) - \cdots +(-1)^{m+1}∑ \limits_{1≤ a_1 <a_2<...<a_m ≤ m+1} N(A_{a_1} ∩ A_{a_2} ∩ \cdots ∩ A_{a_m}) + (-1)^{m+2} N(A_1 ∩ A_2 ∩ \cdots ∩ A_m ∩ A_{m+1})$

since $1≤m≤m$, p(m) is true by inductive hypothesis.

N($A_1 ∪ A_2∪\cdots ∪ A_m$) =
$∑ \limits_{1 ≤ i ≤ m} N(A_{a_1}) - ∑\limits_{1≤a_1<a_2≤m} N(A_{a_1} ∩ A_{a_2}) + ∑\limits_{1≤{a_1}<{a_2}<{a_3}≤m} N(A_{a_1} ∩ A_{a_2} ∩ A_{a_3}) - \cdots + (-1)^{m+1}N(A_1 ∩ A_2 ∩ \cdots ∩ A_m)$

Let B=$A_1 ∪ A_2∪\cdots ∪ A_m$, then the LHS of p(m+1) is $N(B∪A_{m+1})$

Hence $N(B∪A_{m+1}) = N(B)+N(A_{m+1})-N(B∩A_{m+1})$
= $∑ \limits_{1 ≤ {a_1} ≤ m} N(A_{a_1}) - ∑\limits_{1≤a_1<a_2≤m} N(A_{a_1} ∩ A_{a_2}) + ∑\limits_{1≤{a_1}<{a_2}<{a_3}≤m} N(A_{a_1} ∩ A_{a_2} ∩ A_{a_3}) - \cdots + (-1)^{m+1}N(A_1 ∩ A_2 ∩ \cdots ∩ A_m) +N(A_{m+1}) -N((A_1 ∪ A_2∪\cdots ∪A_m)∩A_{m+1}))$
by inductive hypothesis.

Now, in order to prove p(m+1), we should show the last formula driven by the inductive hypothesis equal to RHS of p(m+1). Right?

Then how can we show

$∑ \limits_{1 ≤ {a_1} ≤ m} N(A_{a_1}) - ∑\limits_{1≤a_1<a_2≤m} N(A_{a_1} ∩ A_{a_2}) + ∑\limits_{1≤{a_1}<{a_2}<{a_3}≤m} N(A_{a_1} ∩ A_{a_2} ∩ A_{a_3}) - \cdots + (-1)^{m+1}N(A_1 ∩ A_2 ∩ \cdots ∩ A_m) +N(A_{m+1}) -N((A_1 ∪ A_2∪\cdots ∪A_m)∩A_{m+1}))$

is equal to the following?

$∑ \limits_{1≤ a_1 ≤ m+1} N(A_{a_1}) - ∑ \limits_{1≤ a_1 < a_2 ≤ m+1} N(A_{a_1} ∩ A_{a_2}) + ∑ \limits_{1≤ a_1 < a_2 < a_3 ≤m+1} N(A_{a_1} ∩ A_{a_2} ∩ A_{a_3}) - \cdots +(-1)^{m+1}∑ \limits_{1≤ a_1 <a_2<...<a_m ≤ m+1} N(A_{a_1} ∩ A_{a_2} ∩ \cdots ∩ A_{a_m}) + (-1)^{m+2} N(A_1 ∩ A_2 ∩ \cdots ∩ A_m ∩ A_{m+1})$

• In your statements, you've written union symbols $\cup$ where you want intersection symbols $\cap$. That could be part of your confusion. – user940 Feb 27 '16 at 15:09
• @ByronSchmuland I edited the part. – buzzee Feb 27 '16 at 15:17
• You've done a partial edit. There should be no union symbols on the right hand side of any of those equations. – user940 Feb 27 '16 at 15:19
• You are wrong in proving $P(1)$. E.g.$\sum_{1\leq i<j\leq1}N\left(A_{i}\cap A_{j}\right)=0$ because the summation is empty. There are no tuples $\langle i,j\rangle\in\mathbb{N}$ with $1\leq i<j\leq1$. – drhab Feb 27 '16 at 15:27
• Yikes! You should not have changed the symbols on the left side of the equation! On the left you should have $\cup$, on the right you should have $\cap$. Look at your book again. You will not be able to complete the exercise until you, very slowly and carefully, understand the statement of the inclusion-exclusion principle. – user940 Feb 27 '16 at 15:40

Route to go:

First show that $P\left(1\right)$ and $P\left(2\right)$are both true.

Setting $B:=A_{1}\cup\cdots\cup A_{k}$ by applying $P\left(2\right)$ we find:

$\tag1 N\left(A_{1}\cup\cdots\cup A_{k}\cup A_{k+1}\right)=N\left(B\cup A_{k+1}\right)=N\left(B\right)+N\left(A_{k+1}\right)-N\left(B\cap A_{k+1}\right)$

Under assumption that $P(k)$ is true find expressions for: $$N\left(B\right)=N\left(A_{1}\cup\cdots\cup A_{k}\right)$$ and for $$N\left(B\cap A_{k+1}\right)=N\left(\left(A_{1}\cap A_{k+1}\right)\cup\cdots\cup\left(A_{k}\cap A_{k+1}\right)\right)$$

Substitute these expressions in (1).

edit:

$N\left(B\right)=\sum_{i=1}^{k}N\left(A_{i}\right)-\sum_{1\leq i<j\leq k}N\left(A_{i}\cap A_{j}\right)+\cdots+\left(-1\right)^{k+1}N\left(A_{1}\cap\cdots\cap A_{k}\right)$

$N\left(B\cap A_{k+1}\right)=\sum_{i=1}^{k}N\left(A_{i}\cap A_{k+1}\right)-\cdots+\left(-1\right)^{k+1}N\left(\left(A_{1}\cap A_{k+1}\right)\cap\cdots\cap\left(A_{k}\cap A_{k+1}\right)\right)=\sum_{i=1}^{k}N\left(A_{i}\cap A_{k+1}\right)-\cdots+\left(-1\right)^{k+1}N\left(A_{1}\cap\cdots\cap A_{k}\cap A_{k+1}\right)$

Substitution of this in the (1) gives the following RHS:

$\sum_{i=1}^{k}N\left(A_{i}\right)-\sum_{1\leq i<j\leq k}N\left(A_{i}\cap A_{j}\right)+\cdots+\left(-1\right)^{k+1}N\left(A_{1}\cap\cdots\cap A_{k}\right)+N\left(A_{k+1}\right)-\sum_{i=1}^{k}N\left(A_{i}\cap A_{k+1}\right)+\cdots+\left(-1\right)^{k+2}N\left(A_{1}\cap\cdots\cap A_{k}\cap A_{k+1}\right)$

After a rearrangement of the terms we find:

$N\left(A_{1}\cup\cdots\cup A_{k}\cup A_{k+1}\right)=\sum_{i=1}^{k+1}N\left(A_{i}\right)-\sum_{1\leq i<j\leq k+1}N\left(A_{i}\cap A_{j}\right)+\cdots+\left(-1\right)^{k+2}N\left(A_{1}\cap\cdots\cap A_{k}\cap A_{k+1}\right)$

wich is exactly statement $P\left(k+1\right)$.

• $B:=A$ is commonly used by the introduction/definition of set $B$. If $B$ and $A$ have been introduced/defined already then $B=A$ is an equality that might be observed. – drhab Feb 28 '16 at 8:33
• I guess ":=" is mentioned in more advanced logic or set theory books. Then is it okay to understand "B := A" mean "Define B as A"? – buzzee Feb 28 '16 at 8:46
• Yes, that is the right understanding in this context. – drhab Feb 28 '16 at 11:44
• I've done a proof process for P(1) and P(2), but as for the P(2), it became "$N(A_1\bigcup A_2) = [N(A1)+N(A2)]−2N(A1∪A2)$", not $N(A_1\bigcup A_2) = [N(A1)+N(A2)]−N(A1∪A2)$. So it happened to prove P(2) is not true. I'm not sure whether it's the author's fault on giving a wrong equestion with $\cdots$ or my fault of reading the given equation wrong. – buzzee Feb 28 '16 at 19:31
• $N(A\cup B)=N((A\setminus B)\cup(B\setminus A)\cup(A\cap B))=N(A\setminus B)+N(B\setminus A)+N(A\cap B)$. This because the $3$ sets are disjoint. RHS equals $N(A)+N(B)-N(A\cap B)$. On the left $\cup$ and on the right $\cap$. You did that wrong (again) in your comment. – drhab Feb 29 '16 at 9:16