## Principle of Inclusion and Exclusion

The purpose of this post is to record a small observation about the Principle of Inclusion and Exclusion that I haven’t seen before, but I’m sure must be well known.

Take the usual setup of a finite set $X$ containing subsets $A_1$, $A_2$, $\ldots, A_n$. Let $C = X \backslash (A_1 \cup A_2 \cup \cdots \cup A_n)$. The inclusion-exclusion formula states that

$| C | = \sum_{I \subseteq \{1,2,\ldots, n\}} (-1)^{|I|} |A_I|$

where $A_I = \bigcap_{i \in I} A_i$.

Suppose that we truncate the sum in the inclusion-exclusion formula so that we only sum over sets $I$ of size at most $r$. If $c_r$ denote the resulting integer then

$c_r \le c_{r+2} \le \cdots \le |C| \le \cdots \le c_{r+1} \le c_{r-1}$

for all odd $r \ge n/2$. Thus the $c_r$ eventually provide successively better approximations to $|C| = c_n$.

This result can be proved quite easily by adapting one of the standard proofs of the inclusion-exclusion formula. Let

$f_r(x) = \sum_I (-1)^{|I|} \mathbf{1}_{A_I}(x)$

where the sum is over all $I \subseteq \{1,2,\ldots, n\}$ of size at most $r$ and $\mathbf{1}_{A_I}$ is the indicator function of the set $A_I$. Let $x \in X$. If $x$ belongs to at most $r$ of the sets $A_1, A_2, \ldots, A_r$ then, as in the standard proof, $f_r(x) = 1$ if $x \in C$ and $f_r(x) = 0$ otherwise. Suppose that $x$ belongs to exactly $s > r$ of the sets. Then

$f_r(x) = \sum_{k=0}^r (-1)^k \binom{s}{k} = (-1)^r \binom{s-1}{r}.$

Let $x_s$ be the number of elements of $X$ which belong to exactly $s$ of the sets $A_1, A_2, \ldots, A_n$. We have

$c_r = |C| + (-1)^r e_r$

where

$e_r = \sum_{s > r} \binom{s-1}{r} x_s$

The difference between successive error terms is

$e_{r-1} - e_r = \sum_{s > r} \bigl( \binom{s-1}{r-1} - \binom{s-1}{r} \bigr) x_s + \binom{r-1}{r-1} x_r.$

Since

$\binom{s-1}{r-1} - \binom{s-1}{r} = \binom{s-1}{r-1} \bigl( 1 - \frac{s-r}{r} \bigr) = \binom{s-1}{r-1} \frac{2r-s}{r}$

this shows that the error terms $e_r$ are decreasing for $r \ge n/2$.