0
$\begingroup$

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!

$\endgroup$
2
  • $\begingroup$ How about using exclusion-inclusion principle $\endgroup$ Nov 13, 2016 at 11:25
  • 1
    $\begingroup$ 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)? $\endgroup$
    – Gnuk
    Nov 13, 2016 at 11:27

1 Answer 1

3
$\begingroup$

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}

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .