# Prove the inequality:

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!

• How about using exclusion-inclusion principle – Ashar Tafhim Nov 13 '16 at 11:25
• Suppose you have an element $x \in A$. How many times do you count it on the left hand side? And at least how many times on the right hand side (separate the different cases)? – ToucanNapoleon Nov 13 '16 at 11:27

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}