2
$\begingroup$

Im currently trying to grasp my professors proof for Inclusion-exclusion, and there is one part of his proof that just doesn't make sense to me and I was hoping for some help here.

Theorem:

Let $A_1,A_2, ... , A_n$ be finite sets.

Then $\displaystyle |\cup_{i=1}^n A_i| = \sum_{i=1}^{k} |A_i|- \sum_{i \neq j}|A_i \cap A_j|+ \sum_{i \neq j \neq k}|A_i \cap A_j \cap A_k|-...+(-1)^{n-1}|A_1 \cap ... \cap A_n|$

Proof:

Lemma needed: Let $n \geq 1$, then $\sum_{k=0}^n (-1)^k {n \choose k}= 0$

Proof Lemma: Apply binomial theorem: $(x+y)^n= \sum_{k=0}^n {n \choose k} x^k y^{n-k}$ with $x=-1, y=1$

Proof of the theorem:

Let $x$ be any element of the union. It suffices to show that $x$ is counted exactly once in the sum.

Suppose $x$ belong to $m$ of the $n$ sets $A_i$, for some $1 \leq m \leq n$. Due to symmetry of formula we can assumed WLOG that $x$ belong to $A_1,...,A_m$.

Part where I don't understand below

Then $x$ is counted $(-1)^{k-1}$ times for each $k$-element subset of ${1,2,...,m}$, $1 \leq k \leq m$.

Hence total number of times $x$ is counted is $$\sum_{k=1}^m (-1)^{k-1} {m \choose k} = - \Big( \sum_{k=0}^m (-1)^k {m \choose k} -(-1)^0 {m \choose k} = -(0-1)=1$$

What does he mean that $x$ is counted $(-1)^{k-1}$ times for each k-element subset? I really don't understand where he get that from.

$\endgroup$
4
  • 1
    $\begingroup$ The sign in "counted $(-1)^{k-1}$ times" is taking into account the signs in the inclusion-exclusion formula you're proving. Maybe an easier way to think about it: Since $x$ belongs to $A_1, \dots, A_m$, the $|A_i|$ sum will count $x$ precisely $m = \binom{m}{1}$ times; the $|A_i \cap A_j|$ sum will count it... as many times as you can pick 2 elements from $1, 2, \dots, m$, i.e., $\binom{m}{2}$. The remaining intersections count it $0$ times since at least one of the sets doesn't contain $x$. But the contribution from this second sum is negative, and $(-1)^{k - 1} = (-1)^{2-1}$ does that. $\endgroup$ Aug 29, 2023 at 15:11
  • $\begingroup$ (Incidentally you may want to double check (a) the upper bound on the sum in your inclusion-exclusion and (b) the parentheses and $k$'s in the final display.) $\endgroup$ Aug 29, 2023 at 15:13
  • $\begingroup$ Thanks for your answer, but I feel dumb not understanding it. Would you mind explain it and trying simplify it? And what does he mean by k-element subset? $\endgroup$
    – uoiu
    Aug 29, 2023 at 15:26
  • $\begingroup$ I posted a generalization of Inclustion-Exclusion. It follows similar lines, but perhaps you might find the explanation there more understandable. $\endgroup$
    – robjohn
    Aug 29, 2023 at 16:22

1 Answer 1

3
$\begingroup$

Let's examine the sums in the inclusion-exclusion principle one at a time.

As in the opener, let $x$ be an arbitrary element that belongs to $A_1, A_2, \dots, A_m$ but not $A_{m+1}, \dots, A_n$.

For the first sum, where we have only $k = 1$ sets involved, we are asking how many times $$ \sum_{i = 1}^n | A_i | $$ will count the particular element $x$. Since $x$ belongs to $m$ of the sets but not the remaining $n - m$, it will be counted precisely $m = \binom{m}{1}$ times.

Stepping up slightly in complexity, for the second sum we are asking how many times $x$ will be counted when we are looking at intersections of $k = 2$ sets. That is, in $$ \sum_{i \neq j} | A_i \cap A_j |, $$ how many times is $x$ counted? Well, if $i$ or $j$ isn't equal to one of $1, 2, \dots, m$, then $x$ won't be counted at all since for $x$ to belong to the intersection $A_i \cap A_j$, it must belong to both $A_i$ and $A_j$. Hence the indices $i \neq j$ that make the count of $x$ go up are precisely the ones where both $i$ and $j$ are from $1, 2, \dots, m$. So the new question becomes: how many ways can we pick two different elements from $1, 2, \dots, m$? This is exactly what binomial coefficients do! They count the ways to pick things from sets, there are $\binom{m}{2}$ ways to pick two different things from $m$ things. Hence this second sum counts $x$ exactly $\binom{m}{2}$ times.

However, the second sum in the inclusion-exclusion principle we are trying to prove has a great big negative sign in front of it, so at this point we have in reality counted $x$ $$ \binom{m}{1} \color{red}{-} \binom{m}{2} $$ times.

Continuing this game, when we are asking about the intersections of $k = 3$ sets, for $x$ to be counted it must belong to each of the three, so this boils down to the amount of ways we can pick three elements from $1, 2, \dots, m$, which is $\binom{m}{3}$.

Keep doing this, and we find in the end that $x$ has been counted $$ \binom{m}{1} \color{red}{-} \binom{m}{2} + \binom{m}{3} \color{red}{-} \binom{m}{4} + \dots $$ times. Notice how (a) the number in the bottom of these binomial coefficients goes up by 1 each time, and (b) the sign alternates from $+$ to $-$ to $+$ and so on. Now if you call the number at the bottom $k$, so that we can attempt to write this sum as something of the shape $$ \sum_{k = 1}^m \color{red}{(\text{something with $k$ that makes the alternating signs})} \binom{m}{k}, $$ what should we put in place of the red stuff? Keep in mind that we want the sign to start with $+$ for $k = 1$.

$\endgroup$
6
  • $\begingroup$ Thank you so much for your answer! There is only 2 things I don't understand. When he says "Then $x$ is counted $(-1)^{k-1}$ times for each k-element subset" Is that correct written? Because $x$ is not counted like -1 och 1 times, it should be multiplied with ${m \choose k}$ or some value right? And also, where does the minus sign outside the last sum of my formula come from? Because to me the only thing we changed is the index for $k=1$ to $k=1$ as well as removed the first term, so the minus sign seems to come from nowhere for me. $\endgroup$
    – uoiu
    Aug 29, 2023 at 21:22
  • $\begingroup$ First point, about $(-1)^{k - 1}$ times: it's correct. It's saying that if you pick a $k$-element subset of $1, 2, \dots, m$, meaning you've picked out $k$ specific sets from the collection of the subsets $A_1, A_2, \dots, A_m$, then $x$ will be counted by that collection either $+1$ times or $-1$ times, depending on whether $k$ is even or odd. That's the red stuff in my answer. $\endgroup$ Aug 30, 2023 at 11:31
  • $\begingroup$ Second point, about the minus sign in the final line: Two things change. You change the index of the sum from $k = 1$ to $k = 0$, which mean you have to subtract the $k = 0$ term since it wasn't there to start with. Secondly, the power on $(-1)$ changes from $k - 1$ to $k$, meaning there's an extra minus sign you have to account for. $\endgroup$ Aug 30, 2023 at 11:33
  • $\begingroup$ That said, the final line in your original question is still not correct, see my parenthetical comment to the opening post. $\endgroup$ Aug 30, 2023 at 11:33
  • 1
    $\begingroup$ Precisely right. It's a typo, is all. $\endgroup$ Aug 30, 2023 at 15:27

You must log in to answer this question.

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