Overestimates and underestimates in Inclusion-Exclusion principle In the celebrated Inclusion-Exclusion principle,
$$|\cup A_i|=\sum _i |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}|\cap A_i|$$
if we take only $m \leq n$ items of the right side, then we would get an overestimate if $m$ is odd, and we obtain an underestimate if $m$ is even, for instance,
$$|\cup A_i|\leq \sum _i |A_i|$$
and
$$|\cup A_i|\geq \sum _i |A_i|-\sum _{i<j}  |A_i \cap A_j|.$$
I want an "elementary" proof for this fact which does not use probability or any measure theory. I tried induction, for the second inequality but could not get anything. I would be thankful for the answer or any leading comment in this connection.
Thanks in advance!
 A: Let us introduce some notation. Let
$$
S(n,k)=\sum_{1\le i_1<\dots<i_k\le n} |A_{i_1}\cap \dots \cap A_{i_k}|
$$
The goal is to prove that
$$
\forall m\in \{1,\dots,n\},\quad \begin{matrix}
\text{$m$ is odd}\implies\left|\displaystyle\bigcup_{i=1}^n A_i\right|\le S(n,1)-S(n,2)\dots +S(n,m)\\
\text{$m$ is even}\implies\left|\displaystyle\bigcup_{i=1}^n A_i\right|\ge S(n,1)-S(n,2)\dots -S(n,m)
\end{matrix}\tag{$*$}
$$
The proof is by induction on $n$. The base case $n=1$ is obvious. So, let us assume that $(*)$ is true for $n-1$, and we will prove it for $n$.
Let $m\in \{1,\dots,n\}$ be given. Assume for now that $m$ is odd (the even case is analogous). We start with
$$
\left|\bigcup_{i=1}^n A_i\right|=|A_n|+ \left|\bigcup_{i=1}^{n-1} A_i\right|-\left|\bigcup_{i=1}^{n-1} (A_i \cap A_n)\right|\tag1
$$
This is just $|E\cup F|=|E|+|F|-|E\cap F|$ applied with $E=A_n$ and $F=\bigcup_{i=1}^{n-1}A_n$.
Now, we apply the induction hypothesis twice. First, we apply it to $\left|\bigcup_{i=1}^{n-1} A_i\right|$, using the same $m$, getting
$$
\left|\bigcup_{i=1}^{n-1} A_i\right|\le S(n-1,1)-S(n-1,2)\dots +S(n-1,m)\tag2
$$
Next, we apply the induction hypothesis to the other union $\left|\bigcup_{i=1}^{n-1} (A_i \cap A_n)\right|$. However, this union is being subtracted, so  we instead need a lower bound, so we use $m-1$ instead of $m$. That is,
$$
\left|\bigcup_{i=1}^{n-1} (A_i \cap A_n)\right|\ge T(n-1,1)-T(n-1,2)+\dots -T(n-1,m-1)\tag3
$$
where we define
$$
\begin{align}
T(n-1,k) &:=\sum_{1\le i_1< \dots <i_k\le n-1} |(A_{i_1}\cap A_n)\cap (A_{i_2}\cap A_n)\cap \dots \cap (A_{i_k}\cap A_n)|
\\
T(n-1,0) &:= 0
\end{align}
$$
Combining $(1)$, $(2)$ and $(3)$, we get
$$
\left|\bigcup_{i=1}^{n} A_i\right|\le \sum_{k=1}^{m} (-1)^{k-1}\Big(S(n-1,k)+T(n-1,k-1)\Big)\tag4
$$
To complete the proof, you just need to realize that
$$
\forall k\in \{1,\dots,n\}\qquad S(n,k)=S(n-1,k)+T(n-1,k-1)\tag5
$$
This is true because $S(n-1,k)$ consists of the summands in $S(n,k)$ which do not involve $A_n$, while $T(n-1,k-1)$ is the summands in $S(n,k)$ which do involve $A_n$. The only exception to this is the case $k=1$; here, we instead use $S(n,1)=S(n-1,1)+|A_n|$, which is valid because there is an $|A_n|$ floating out front in $(1)$.
Anyways, if you apply $(5)$ to $(4)$, then $(4)$ becomes $(*)$ exactly. QED (at least when $m$ is odd; when $m$ is even, just flip all inequality signs).
A: dIt is enough to prove the inequalities of indicators $$1_{A} \leq \sum_{i}1_{A_i},$$
$$1_{A} \geq \sum_{i}1_{A_i} - \sum_{i < j}1_{A_i \cap A_j},$$
$$1_{A} \leq \sum_{i}1_{A_i} - \sum_{i < j}1_{A_i \cap A_j} + \sum_{i < j < k}1_{A_i \cap A_j \cap A_k},$$
etc. Because if these inequalities are shown, then evaluating and summing them over all $\omega \in A_1 \cup \dots \cup A_n$ finishes the proof.
So suppose $\omega \in A_1 \cup \dots \cup A_n$ is arbitray. So $\omega$ is in $k \geq 1$ of the sets. Then for odd $m$, we want to show that $$1 \leq k - \binom{k}{2} + \binom{k}{3} - \dots \pm \binom{k}{m},$$
and for even $m$ we want to show the reverse inequality. So we want to show that
$$\sum_{i = 0}^{m}(-1)^i\binom{k}{i} \leq 0$$
for odd $m$, and the reverse inequality for even $m$. But this follows from the formula
$$\sum_{i = 0}^{m}(-1)^i\binom{k}{i} = (-1)^m\binom{k - 1}{m}.$$
A: Let $A = A_1 \cup \cdots \cup A_n$. We first partition $A$ according to the value of $(\mathbf{1}_{A_i}, \ldots, \mathbf{1}_{A_n})$. More specifically, for each $\varepsilon \in \{ 0, 1\}^n$ we define $A_{\varepsilon}$ as
\begin{align*}
A_{\varepsilon}
= \{ \omega \in A : \mathbf{1}_{A_i}(\omega) = \varepsilon_i \text{ for all } i = 1, \ldots, n\}
= \bigcap_{i=1}^{n} A_{i,\varepsilon_i},
\end{align*}
where $A_{i,1} = A_i$ and $A_{i,0} = A\setminus A_i$ for each $i = 1, \ldots, n$. In other words, $A_{\varepsilon}$ is the set of all $\omega \in A$ such that $[\omega \in A_i \iff \varepsilon_i = 1]$ holds for all $i = 1, \ldots, n$. Then it is clear that
$$ A_j
= \{ \omega \in A : \mathbf{1}_{A_j}(\omega) = \varepsilon_j\}
= \bigcup_{\substack{\varepsilon \in \{0, 1\}^n \\ \varepsilon_j = 1}} A_{\varepsilon}. $$
Using this, we can rewrite the (unsigned) $k$-th term $S_k$ in the inclusion-exclusion formula as:
\begin{align*}
S_k
:= \sum_{i_1 < \ldots < i_k} |A_{i_1} \cap \cdots \cap A_{i_k}|
&= \sum_{i_1 < \ldots < i_k} \Biggl( \sum_{\varepsilon \in \{0, 1\}^n} |A_{\varepsilon}| \cdot \mathbf{1}_{\{\varepsilon_{i_1} = 1, \ldots, \varepsilon_{i_k} = 1\}} \Biggr) \\
&= \sum_{\varepsilon \in \{0, 1\}^n} |A_{\varepsilon}| \Biggl( \sum_{i_1 < \ldots < i_k} \mathbf{1}_{\{\varepsilon_{i_1} = 1, \ldots, \varepsilon_{i_k} = 1\}} \Biggr) .
\end{align*}
The parenthesized sum in the last line counts the number $k$-subsets of $\{i : \varepsilon_i = 1\}$, and so, it is evaluated as $\binom{|\varepsilon|}{k}$, where $|\varepsilon| = \varepsilon_1 + \cdots + \varepsilon_n$. So, the above double sum for $S_k$ is reduced to
\begin{align*}
S_k
&= \sum_{\varepsilon \in \{0, 1\}^n} \binom{|\varepsilon|}{k} |A_{\varepsilon}|. \tag{1}
\end{align*}
Using this, the sum of first $m$ terms in the inclusion-exclusion principle is given by
$$ \sum_{k=1}^{m} (-1)^{k-1} S_k
= \sum_{\varepsilon \in \{0, 1\}^n} \Biggl[ \sum_{k=1}^{m} (-1)^k \binom{|\varepsilon|}{k} \Biggr] |A_{\varepsilon}|. \tag{2} $$
To make use of this equality, we note that
\begin{align*}
\sum_{k=1}^{m} (-1)^{k-1} \binom{r}{k}
&= \sum_{k=1}^{m} (-1)^{k-1} \left[ \binom{r-1}{k-1} + \binom{r-1}{k} \right] \\
&= 1 + (-1)^{m-1}\binom{r-1}{m}
\ \begin{cases}
\geq 1, & \text{if $m$ is odd,} \\
\leq 1, & \text{if $m$ is even.}
\end{cases} \tag{3}
\end{align*}
So by plugging $\text{(3)}$ to $\text{(2)}$, we conclude:
\begin{align*}
\text{$m$ odd}
&\quad\implies\quad
\sum_{k=1}^{m} (-1)^{k-1} S_k \geq \sum_{\varepsilon \in \{0, 1\}^n} |A_{\varepsilon}| = |A|, \\
\text{$m$ even}
&\quad\implies\quad
\sum_{k=1}^{m} (-1)^{k-1} S_k \leq \sum_{\varepsilon \in \{0, 1\}^n} |A_{\varepsilon}| = |A|.
\end{align*}
