91Ó°ÊÓ

Let's consider the case when we have only one set. In this case, according to the inclusion/exclusion principle, we should have: $$ N(A_1) = N(A_1) $$ Since the principle works for \(n=1\), we can proceed to the induction step.

Assume that the general inclusion/exclusion principle holds for \(n=k\). We'll use this assumption to prove the principle for \(n=k+1\).

Let's consider \(k+1\) finite sets \(A_1, A_2, \ldots, A_{k+1}\). Let \(B = A_1 \cup A_2 \cup \ldots \cup A_k\). According to the induction hypothesis, we know that: $$ N(B) = \sum_{1 \leq i \leq k} N(A_i) - \sum_{1 \leq i \leq j \leq k} N(A_i \cap A_j) + \sum_{1 \leq j < j < k \leq k} N(A_i \cap A_j \cap A_k) - \cdots + (-1)^{k+1} N(A_1 \cap A_2 \cap \cdots \cap A_k) $$ Now, let us find \(N(B \cup A_{k+1})\). We can use the induction hypothesis again for sets \(B\) and \(A_{k+1}\). We have: $$ N(B \cup A_{k+1}) = N(B) + N(A_{k+1}) - N(B \cap A_{k+1}) $$ To find \(N(B \cap A_{k+1})\), we apply the inclusion/exclusion principle for \(n=k\) on the sets \(A_1 \cap A_{k+1}, \ldots, A_k \cap A_{k+1}\): $$ N(B \cap A_{k+1}) = \sum_{1 \leq i \leq k}N(A_i \cap A_{k+1}) - \sum_{1 \leq i < j \leq k} N(A_i \cap A_j \cap A_{k+1}) + \cdots + (-1)^{k+1} N(A_1 \cap A_2 \cap \cdots \cap A_{k+1}) $$ Now, substituting this expression back into the equation for \(N(B \cup A_{k+1})\) gives: $$ N(B \cup A_{k+1}) = N(B) + N(A_{k+1}) - N(B \cap A_{k+1}) $$ Combining the expressions for \(N(B)\) and \(N(B \cap A_{k+1})\), we get: $$ N(B \cup A_{k+1}) = \sum_{1 \leq i \leq k+1} N(A_i) - \sum_{1 \leq i \leq j \leq k+1} N(A_i \cap A_j) + \sum_{1 \leq j < j < k \leq k+1} N(A_i \cap A_j \cap A_k) - \cdots + (-1)^{(k+1)+1} N(A_1 \cap A_2 \cap \cdots \cap A_{k+1}) $$ This proves the general inclusion/exclusion principle for the case \(n=k+1\), and by induction, we have shown that the principle is valid for all positive integers \(n\).