"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})$
Best Answer
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)$.