Let $A_i, A_2, ..., A_n$ be finite sets and let $A = A_1 \cup A_2 \cup...\cup A_n$. prove:
$$ |A| \leq\ \sum_{i=1}^n |A_i|-(n-1)|A_1 \cap A_2 \cap...\cap A_n| $$
Thanks for any tips/proof! Been struggling on this one for a while!
Let $A_i, A_2, ..., A_n$ be finite sets and let $A = A_1 \cup A_2 \cup...\cup A_n$. prove:
$$ |A| \leq\ \sum_{i=1}^n |A_i|-(n-1)|A_1 \cap A_2 \cap...\cap A_n| $$
Thanks for any tips/proof! Been struggling on this one for a while!
Observe that $$ A = A_1 \cup (A_2 - A_1) \cup (A_3 - (A_1 \cup A_2) \cup \cdots $$ in which $A_1,\ A_2 - A_1,\ A_3 - (A_1 \cup A_2),\ \cdots\ $ are disjoint. Therefore, \begin{align} A &= |A_1| + |A_2 - A_1| + |A_3 - (A_1 \cup A_2)| + \cdots \\ & \leq |A_1| + (|A_2| - |A_1 \cap A_2|) + (|A_3| - |A_1 \cap A_2 \cap A_3|) + \cdots \\ & \leq |A_1| + (|A_2| - |A_1 \cap \cdots \cap A_n|) + (|A_3| - |A_1 \cap \cdots \cap A_n|) + \cdots \\ &= \sum_{i=1}^n |A_i| - (n-1)|A_1 \cap A_2 \cap \cdots \cap A_n| \end{align}