I am trying to demonstrate the principle of inclusion - exclusion for n elements. For n = 2 and n = 3 I have calculated it applying properties of monotonicity, dimension, complementarity and it gives me correctly, but when looking for a generalization for n elements using induction I can not get out of the beginning.
$$\sum_{i=1}^n (A_i)+ \sum_{i c j} (A_{i1} ∩ A_{i2})+ ... + (−1)^{n-1} (A_{i1} ∩ ... ∩ A_{ik})$$
Could someone help me by showing me the way forward? I've been trying it for a while and I do not know how to get out
Of course this is true for $n=1$, suppose it is true for all $k\leq n$, then \begin{align*} |A_1\cup A_2\cup \dots \cup A_n\cup A_{n+1}| &= |(A_1\cup A_2\cup \dots \cup A_n)\cup A_{n+1}|\\ &=|A_1\cup A_2\cup \dots \cup A_n| + |A_{n+1}| - |(A_1\cup A_2\cup \dots \cup A_n)\cap A_{n+1}|\\ &=|A_1\cup A_2\cup \dots \cup A_n| + |A_{n+1}| \\&- |(A_1\cap A_{n+1})\cup (A_2\cap A_{n+1})\cup \dots \cup (A_n\cap A_{n+1})|\\ \end{align*}
Where the second line is the inclusion exclusion principle for $k=2$. Now we can apply it again for the first and last term with $k=n$ to get respectively $$\sum_{k = 1}^n (-1)^{k+1} \left( \sum_{1 \leq i_1 < \cdots < i_k \leq n} | A_{i_1} \cap \cdots \cap A_{i_k} | \right)$$ and \begin{align*} &\sum_{k = 1}^n (-1)^{k+1} \left( \sum_{1 \leq i_1 < \cdots < i_k \leq n} | (A_{i_1}\cap A_{n+1}) \cap \cdots \cap (A_{i_k}\cap A_{n+1}) | \right)\\ =&\sum_{k = 1}^n (-1)^{k+1} \left( \sum_{1 \leq i_1 < \cdots < i_k \leq n} | A_{i_1} \cap \cdots \cap A_{i_k}\cap A_{n+1} | \right) \end{align*} Putting everything together we get \begin{align*} &|A_1\cup A_2\cup \dots \cup A_n\cup A_{n+1}|\\ =&\sum_{k = 1}^n (-1)^{k+1} \left( \sum_{1 \leq i_1 < \cdots < i_k \leq n} | A_{i_1} \cap \cdots \cap A_{i_k} | \right) + |A_{n+1}| - \sum_{k = 1}^n (-1)^{k+1} \left( \sum_{1 \leq i_1 < \cdots < i_k \leq n} | A_{i_1} \cap \cdots \cap A_{i_k}\cap A_{n+1} | \right)\\ =&\sum_{k = 1}^n (-1)^{k+1} \left( \sum_{1 \leq i_1 < \cdots < i_k \leq n} | A_{i_1} \cap \cdots \cap A_{i_k} | \right)+ |A_{n+1}| + \sum_{k = 2}^{n+1} (-1)^{k+1} \left( \sum_{\substack{1 \leq i_1 < \cdots < i_k \leq n+1\\i_k=n+1}} | A_{i_1} \cap \cdots \cap A_{i_k} | \right)\\ =&\sum_{k = 1}^{n+1} (-1)^{k+1} \left( \sum_{\substack{1 \leq i_1 < \cdots < i_k \leq n+1\\i_k\neq n+1}} | A_{i_1} \cap \cdots \cap A_{i_k} | \right) + \sum_{k = 1}^{n+1} (-1)^{k+1} \left( \sum_{\substack{1 \leq i_1 < \cdots < i_k \leq n+1\\i_k=n+1}} | A_{i_1} \cap \cdots \cap A_{i_k} | \right)\\ =&\sum_{k = 1}^{n+1} (-1)^{k+1} \left( \sum_{\substack{1 \leq i_1 < \cdots < i_k \leq n+1\\i_k\neq n+1}} | A_{i_1} \cap \cdots \cap A_{i_k} | + \sum_{\substack{1 \leq i_1 < \cdots < i_k \leq n+1\\i_k=n+1}} | A_{i_1} \cap \cdots \cap A_{i_k} | \right)\\ =&\sum_{k = 1}^{n+1} (-1)^{k+1} \left( \sum_{1 \leq i_1 < \cdots < i_k \leq n+1} | A_{i_1} \cap \cdots \cap A_{i_k} | \right)\\ \end{align*} Going to the third line we add $k=n+1$ to the summation since it contains no terms.
This finishes the proof by induction there for you get the inclusion exclusion principle.