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

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

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

$$\sum_{i; Exclude the cardinalities of the pairwise intersections.

$$\sum_{i; 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?

• Plus and minus, according to the parity of $n$. You have to consider that the "equation" is about number of elements of sets; thus, the formula is a sum. Commented Apr 14, 2022 at 13:36
• @Mauro ALLEGRANZA It is true that the OP hasn't mentionned that. But I think that for him/her it's implicit. The more general framework in which we have such a formula is measure theory with application in probability... but I don't think this was the target of the question. Commented Apr 14, 2022 at 13:48

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.

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.

• A solid explanation! I don't think I've seen a proof of this principle that goes in so much depth. I was so confused until I saw this answer. Thank you so much! Commented Mar 30, 2023 at 13:22