Inclusion–exclusion principle; what is $(-1)^{n+1}$

Question

could somebody kindly confirm that my understanding of inclusion-exclusion matches it's formula.

for a 3 sets example; we add 3 unions, subtract the total of all 3 pairwise intersections and add the triple-wise intersections as such; $A_1\cup A_2\cup A_3= A_1+A_2+A_3-A_1\cap A_2 - A_1\cap A_3-A_2\cap A_3+A_1\cap A_2\cap A_3$
in summary, it is adding all sets, subtract the over-count and adding back the "over-subtract"

for multiple sets; $ \bigcup_{i=1}^n A_i = \sum_{i=1}^n A_i - \sum_{i<j} A_i \cap A_j + \sum_{i<j<k} A_i \cap A_j \cap A_k - \dots + (-1)^{n+1} A_i \cap \dots A_n$

$\sum_{i=1}^n A_i $; Include the cardinalities of the sets

$\sum_{i<j} A_i \cap A_j $; Exclude the cardinalities of the pairwise intersections.

$\sum_{i<j<k} A_i \cap A_j \cap A_k $; Include the cardinalities of the triple-wise intersections.
$\dots$
$(-1)^{n+1} A_i \cap \dots A_n $; Include cardinality of the $n$-tuple-wise intersection.

If the above are correct, what does $(-1)^{n+1}$ represents?

kindly advise. Thank you

Answer 1

This $(-1)^{n+1}$ switches between $+1$ and $-1$ each time you increment $n$, starting with $+1$ when $n=1$. What it says about the counting is that you add the cardinalities of the $n$-fold intersections if $n$ is odd and subtract them if $n$ is even.

Answer 2

Unclear if this response is on point. Anyway...

When I was introduced to Inclusion-Exclusion, what I really wondered was: Why is the formula valid?

The following explanation doesn't seem to be readily available, at this level of detail. So...

For any set $E$ with a finite number of elements, let $|E|$ denote the number of elements in $E$.

Suppose that you have $n$ sets $A_1, A_2, \cdots, A_n$ and you want to compute $|A_1 \cup A_2 \cup \cdots \cup A_n|$.

Consistent with the OP's (original poster's) description,
for $r \in \{1,2,\cdots, n\}$
let $T_r$ denote $~\displaystyle \sum_{1 \leq i_1 < i_2 < \cdots < i_r \leq n} |A_{i_1} \cap A_{i_2} \cap \cdots \cap A_{i_r}|.$

That is, $T_r$ represents the sum of $~\displaystyle \binom{n}{r}$ terms.

Then, according to the formula,

$$|A_1 \cup A_2 \cup \cdots \cup A_n| = \sum_{r=1}^n (-1)^{r+1}T_r. \tag1 $$

So, the question is: why is the formula given in (1) above valid?

To answer that, first you need a preliminary result:

PR-1
For $\displaystyle j \in \Bbb{Z^+},~\sum_{i=1}^j (-1)^{i+1} \binom{j}{i} = 1.$
Proof:
By binomial expansion, $~\displaystyle 0 = (0)^j = [(1) + (-1)]^j = \sum_{i=0}^j (-1)^i \binom{j}{i}.$
So, the desired result comes from recognizing that the difference between the line above, and the PR-1 assertion is that:

• the $~\displaystyle (-1)^0 \binom{j}{0} = 1~$ term has been omitted.
• each of the remaining terms has been multiplied by an additional factor of $(-1)$.

---

For each element in $x$ in $A_1 \cup A_2 \cup \cdots \cup A_n$,
there will exist some positive integer
$j \in \{1,2,\cdots,n\}$ such that $x$ is in exactly $j$ of the subsets $A_1, A_2, \cdots, A_n$.
Without loss of generality, assume that the element $x$ is in each of $A_1, A_2, \cdots, A_j$ and that the element $x$ is not present in any of $A_{j+1}, A_{j+2}, \cdots, A_n$.

This means that for each value of $r$ in $\{1,2,\cdots,j\}$,
when $T_r$ is computed, the effect with respect to the element $x$ will be that this element contributes $~\displaystyle \binom{j}{r}~$ to the value $T_r.$

By this I mean that of the $~\displaystyle \binom{n}{r}~$ terms in the computation of $T_r$, the element $x$, which is in exactly $j$ of the subsets, will be represented in $~\displaystyle \binom{j}{r}~$ of the terms. What this implies is that when $T_r$ is computed, the effect is that the element $x$ is counted $~\displaystyle \binom{j}{r}~$ times.

Further, for each $r$ in $\{j+1, j+2, \cdots, n\}$,
when $T_r$ is computed, the effect with respect to the element $x$ will be that this element contributes $0$ to the value $T_r$. This is because it is being assumed that the element $x$ is only in exactly $j$ of the subsets.

Therefore, with respect to the individual element $x$, when the formula in (1) above is applied, the effect will be that the number of times that the element $x$ is counted is

$$ ~\sum_{i=1}^j (-1)^{i+1} \binom{j}{i}. \tag2 $$

By PR-1, the overall effect is that this element $x$ has been counted exactly once.

Further, this applies to any element
$x$ in $A_1 \cup A_2 \cup \cdots \cup A_n$
specifically because PR-1 holds for each $j \in \Bbb{Z^+}$
and, as indicated,
for each element $x$ in $A_1 \cup A_2 \cup \cdots \cup A_n$
there exists a positive integer $j$ such that the element $x$ is in exactly $j$ of the $n$ subsets.

So, the overall effect of the formula in (1) above is that each individual element $x$ in $A_1 \cup A_2 \cup \cdots \cup A_n$ is counted exactly once.