1
$\begingroup$

Suppose that $A_1, . . . , A_k$ is a collection of $k ≥ 2$ sets. Show that (using induction),

$$\big| \bigcup\limits_{i=1}^{k}A_i \big| \ge \sum\limits_{i=1}^{k} \big|A_i| - \sum\limits_{\{i,j\}} \big|A_i \cap A_j \big| $$

where the second term on the right sums over all subsets of [k] of size 2.

I must prove this by induction.

Take the base case $k = 2$,

$$ LHS = |A_1| + |A_2| - |A_1 \cap A_2|$$

$$RHS = |A_1| + |A_2| - 2|A_1 \cap A_2|$$

$$\implies LHS > RHS$$

So the base case $k=2$ holds!

Now consider $k$ true.

Take $k+1$,

$$\big| \bigcup\limits_{i=1}^{k+1}A_i \big| \ge \sum\limits_{i=1}^{k+1} \big|A_i| - \sum\limits_{\{i,j\}} \big|A_i \cap A_j \big| $$

Now, I know the LHS can be written as,

$$\big| \bigcup\limits_{i=1}^{k+1}A_i \big| = \sum_{0 \neq I \subseteq [k+1]}(-1)^{|I| + 1} \big| \bigcap\limits_{i \in I} A_i \big|$$

However, I'm stuck trying to play around with both the LHS and RHS to make the inequality hold for $k+1$. Could someone please offer a trick I could use?

$\endgroup$

1 Answer 1

2
$\begingroup$

Your argument for the base case isn’t quite right: the sum $\sum_{\{i,j\}}|A_i\cap A_j|$ is taken over all $2$-element subsets of $[k]$, not over all ordered pairs of elements of $[k]$, or even all ordered pairs of distinct elements of $[k]$. Thus, for $k=2$ the righthand side is $|A_1|+|A_2|-|A_1\cap A_2|$, not $|A_1|+|A_2|-2|A_1\cap A_2|$: you don’t count the pair $\{1,2\}$ twice. The base case holds because the lefthand and righthand sides are equal, not because the lefthand side is greater than the righthand side.

A small point about correct usage: it makes no sense to say that you’re assuming that $k$ is true, because $k$ is not a statement and therefore is not even the kind of thing that can be true or false. What you mean is that you are assuming that the inequality in question holds for $k$.

As for the induction step itself, going back to the inclusion-exclusion formula is unnecessary: this is a result that would actually be appropriate as part of the preparation for the inclusion-exclusion principle. What you can do instead is temporarily amalgamate $A_k$ and $A_{k+1}$ into a single set; then

$$\begin{align*} \left\vert\bigcup_{i=1}^{k+1}A_i\right\vert&=\left\vert\left(\bigcup_{i=1}^{k-1}A_i\right)\cup(A_k\cup A_{k+1})\right\vert\\ &\overset{(1)}\ge\left\vert\left(\bigcup_{i=1}^{k-1}A_i\right)\right\vert+\vert A_k\cup A_{k+1}\vert\\ &\overset{(2)}\ge\sum_{i=1}^{k-1}|A_i|+|A_k\cup A_{k+1}|\\ &\overset{(1)}\ge\sum_{k=1}^{k+1}|A_i|\;, \end{align*}$$

where the inequalities $(1)$ follow from the base case, and the inequality $(2)$ follows from the induction hypothesis.

Added: I’m going to leave that as an illustration of how easy it is inadvertently to make something a little harder than necessary. In fact we could just observe that

$$\begin{align*} \left\vert\bigcup_{i=1}^{k+1}A_i\right\vert&=\left\vert\left(\bigcup_{i=1}^k A_i\right)\cup A_{k+1}\right\vert\\ &\overset{(1)}\ge\left\vert\left(\bigcup_{i=1}^k A_i\right)\right\vert+\vert A_{k+1}\vert\\ &\overset{(2)}\ge\sum_{i=1}^{k+1}|A_i|\;. \end{align*}$$

$\endgroup$
1
  • $\begingroup$ Very nice sir! Thank sir! $\endgroup$ May 10, 2020 at 22:06

You must log in to answer this question.

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