# Inclusion-exclusion-like fractional sum is positive?

Let $A_1,A_2,\ldots,A_n$ be finite nonempty sets. Is it true that
$$\sum_{i=1}^n\frac{1}{|A_i|}-\sum_{1\leq i<j\leq n}\frac{1}{|A_i\cup A_j|}+\sum_{1\leq i<j<k\leq n}\frac{1}{|A_i\cup A_j\cup A_k|}-\cdots+\frac{(-1)^{n-1}}{|A_1\cup\cdots\cup A_n|}$$ is always positive?

For $n=1$ this is obvious.
For $n=2$ it is true because $\frac{1}{|A_1|}\geq\frac{1}{|A_1\cup A_2|}$ and $\frac{1}{|A_2|}>0.$

For $n=3$ it is true because $\frac{1}{|A_1|}\geq\frac{1}{|A_1\cup A_2|}$, $\frac{1}{|A_2|}\geq\frac{1}{|A_2\cup A_3|}$, $\frac{1}{|A_3|}\geq\frac{1}{|A_3\cup A_1|}$, and $\frac{1}{|A_1\cup A_2\cup A_3|}>0$.

But for $n=4$ this reasoning ceases to hold.

#### Solutions Collecting From Web of "Inclusion-exclusion-like fractional sum is positive?"

Here is an analytic proof inspired by the one in

We fix a positive integer $n$. We let $\left[ n\right]$ denote the set
$\left\{ 1,2,\ldots,n\right\}$.

We first show an auxiliary result:

Theorem 1. Let $A_{1},A_{2},\ldots,A_{n}$ be $n$ finite nonempty sets. Let
$x\in\left( 0,1\right)$. Then,

$0<\sum\limits_{I\subseteq\left[ n\right] }\left( -1\right) ^{\left\vert I\right\vert }x^{\left\vert \bigcup_{i\in I}A_{i}\right\vert }<1$.

Proof of Theorem 1. Let $A$ be the set $A_{1}\cup A_{2}\cup\cdots\cup A_{n}$. Let $X$ be the set of all maps $A\rightarrow\left\{ 0,1\right\}$. We
make $X$ into a probability space by assigning to a map $f:A\rightarrow \left\{ 0,1\right\}$ the probability $x^{\left\vert f^{-1}\left( 1\right) \right\vert }\left( 1-x\right) ^{\left\vert f^{-1}\left( 0\right) \right\vert }$. This probability space $X$ is precisely the $\left\vert A\right\vert$-th Cartesian power of the probability space $\left\{ 0,1\right\}$ where $1$ has probability $x$ and $0$ has probability $1-x$. In
simpler terms, randomly sampling a point in $X$ is tantamount to constructing
a map $A\rightarrow\left\{ 0,1\right\}$ by flipping an $x$-coin for every
$a\in A$ (independently), and letting the map $A\rightarrow\left\{ 0,1\right\}$ send $a$ to $1$ if the $x$-coin has brought up heads and to $0$
if it has brought up tails. Here, an “$x$-coin” means a biased coin which brings up heads with
probability $x$.

Now, let $Y\subseteq X$ be the set of all maps $f:A\rightarrow\left\{ 0,1\right\}$ such that every $i\in\left\{ 1,2,\ldots,n\right\}$ satisfies
$0\in f\left( A_{i}\right)$. Then, $Y$ is the set of all maps
$f:A\rightarrow\left\{ 0,1\right\}$ such that no $i\in\left\{ 1,2,\ldots,n\right\}$ satisfies $A_{i}\subseteq f^{-1}\left( 1\right)$.
Thus, the probability of $Y$ (as an event in the probability space $X$) can be
computed by the principle of inclusion and exclusion to be $\sum\limits _{I\subseteq\left[ n\right] }\left( -1\right) ^{\left\vert I\right\vert }x^{\left\vert \bigcup_{i\in I}A_{i}\right\vert }$. But this probability is
$>0$ (since the “constant-$0$” map belongs
to $Y$ and has nonzero probability) and $<1$ (since the “constant-$1$”
map does not belong to $Y$, and still has
nonzero probability). Thus, Theorem 1 follows.

(Please correct all stochastics terminology that I have butchered. I have not
used probability spaces since I passed probability 101 some 9 years ago.)

Theorem 2. Let $A_{1},A_{2},\ldots,A_{n}$ be $n$ finite nonempty sets. Let
$x\in\left( 0,1\right)$. Then,

$\sum\limits_{\substack{I\subseteq\left[ n\right] ;\\I\neq\varnothing}}\left( -1\right) ^{\left\vert I\right\vert -1}\dfrac{1}{\left\vert \bigcup_{i\in I}A_{i}\right\vert }>0$.

Proof of Theorem 2. Theorem 1 shows that every $x\in\left( 0,1\right)$ satisfies

$1>\sum\limits_{I\subseteq\left[ n\right] }\left( -1\right) ^{\left\vert I\right\vert }x^{\left\vert \bigcup_{i\in I}A_{i}\right\vert }$

$=1+\sum\limits_{\substack{I\subseteq\left[ n\right] ;\\I\neq\varnothing}}\left( -1\right) ^{\left\vert I\right\vert }x^{\left\vert \bigcup_{i\in I} A_{i}\right\vert }$ (here, we have split the $I=\varnothing$ term out of the sum)

$=1-\sum\limits_{\substack{I\subseteq\left[ n\right] ;\\I\neq\varnothing}}\left( -1\right) ^{\left\vert I\right\vert -1}x^{\left\vert \bigcup_{i\in I} A_{i}\right\vert }$.

In other words, every $x\in\left( 0,1\right)$ satisfies

$\sum\limits_{\substack{I\subseteq\left[ n\right] ;\\I\neq\varnothing}}\left( -1\right) ^{\left\vert I\right\vert -1}x^{\left\vert \bigcup_{i\in I} A_{i}\right\vert }>0$.

We denote the left hand side of this inequality by $f\left( x\right)$.
Then, we thus have shown that every $x\in\left( 0,1\right)$ satisfies
$f\left( x\right) >0$. Hence, $\int_{0}^{1}\dfrac{f\left( x\right) } {x}dx>0$. But the definition of $f$ (and the rule that $\int_{0}^{1} \dfrac{x^{m}}{x}dx=\dfrac{1}{m}$ for every $m\geq1$) yields $\int_{0} ^{1}\dfrac{f\left( x\right) }{x}dx=\sum\limits_{\substack{I\subseteq\left[ n\right] ;\\I\neq\varnothing}}\left( -1\right) ^{\left\vert I\right\vert -1}\dfrac{1}{\left\vert \bigcup_{i\in I}A_{i}\right\vert }$. Hence,
$\sum\limits_{\substack{I\subseteq\left[ n\right] ;\\I\neq\varnothing}}\left( -1\right) ^{\left\vert I\right\vert -1}\dfrac{1}{\left\vert \bigcup_{i\in I}A_{i}\right\vert }>0$, and Theorem 2 is proven.

I don’t understand your justification for why this is true even for $n=2$ (more strongly, I think it’s false). It’s certainly the case that $\left|A_1\right|^{-1} \ge \left|A_1 \cup A_2\right|^{-1}$, but there are more terms in the sum over pairs of sets than in the sum over sets, so comparing individual terms doesn’t guarantee anything about the sign of the outcome. For instance, let $A_1=\{1,2,3\}$, $A_2=\{1,2,4\}$, $A_3=\{1,3,4\}$, and $A_4=\{2,3,4\}$. Then every $\left|A_i\right|=3$, and every $\left|A_i\cup A_j\right|=4$, so
$$\sum_{i=1}^{4}\frac{1}{\left|A_i\right|} – \sum_{1\le i<j\le 4}\frac{1}{\left|A_i\cup A_j\right|}=4\times\frac{1}{3}-6\times\frac{1}{4}=-\frac{1}{6} < 0.$$
Am I missing something?

Here is an extended comment:

It seems true for $n$ odd, for reasons similar to the ones given in the $n=3$ case. To see this, we first consider the first $n-1$ summands, and pair sum $i$, $1\leq i<n/2$, with sum $n-i$. Note that there are an equal number of terms these pairs, as
$$\binom{n}{i}=\binom{n}{n-i}$$
Now we pair up elements from each sum. Namely, we have to find a bijection taking $\{A_{j_1},\dots,A_{j_i}\}$ to a superset $\{A_{k_1},\dots,A_{k_{n-i}}\}$. If we can do this, then we know
$$\left|\cup_i A_{j_i}\right|\leq \left|\cup_i A_{k_i}\right|,\text{ or }\;\frac{1}{\left|\cup_i A_{j_i}\right|}\geq\frac{1}{\left|\cup_i A_{k_i}\right|}$$
and from this pairing it follows that the $i$th sum minus the $(n-i)$th sum is nonnegative. Adding on the final $n$th term, which is positive, will then ensure that the whole sum is positive.

(Hopefully the above argument makes sense. If it does not, feel free to leave a comment and I can expand on it, for now I will move on.)

So now it suffices to find such a bijection. I am unfortunately having trouble rigorously showing there is one, but heuristically it seems like there must be such a map. Hopefully that helps a bit, and I will keep thinking on it and see if I can finish it up.

He refers to a very elegant answer by @zeraouliarafik regarding the strongly related inequality question:

Let $x_1,\ldots,x_n> 0$. Does the following inequality hold?
\begin{align*}
\sum_{i=1}^n\frac{1}{x_i}-\sum_{i<j}\frac{1}{x_i+x_j}+\sum_{i<j<k}\frac{1}{x_i+x_j+x_k}-\cdots
\end{align*}

Observe, that OPs question is a generalisation of (1). In the following we consider two extreme cases:

Case 1: Sets $A_1,\ldots,A_n$ forming a partition

Let’s assume the sets $A_i, 1\leq i \leq n$ form a partition of a set $X\neq \emptyset$.

Then OPs inequality becomes
\begin{align*}
\sum_{i=1}^n&\frac{1}{|A_i|}-\sum_{1\leq i<j\leq n}\frac{1}{|A_i\cup A_j|}+\sum_{1\leq i<j<k\leq n}\frac{1}{|A_i\cup A_j\cup A_k|}-\cdots+\frac{(-1)^{n-1}}{|A_1\cup\cdots\cup A_n|}\\
&=\sum_{i=1}^n\frac{1}{|A_i|}-\sum_{1\leq i<j\leq n}\frac{1}{|A_i|+|A_j|}+\sum_{1\leq i<j<k\leq n}\frac{1}{|A_i|+|A_j|+|A_k|}-\cdots+\frac{(-1)^{n-1}}{|A_1|+\ldots+|A_n|} > 0\tag{2}\\
\end{align*}
which is exactly (1) and already proven by @zeraouliarafik in the referenced MSE inequality question.

On the other side we have the extreme case

Case 2: Identical sets $X=A_1=\ldots=A_n\neq \emptyset$

Then OPs inequality becomes

\begin{align*}
\sum_{i=1}^n&\frac{1}{|A_i|}-\sum_{1\leq i<j\leq n}\frac{1}{|A_i\cup A_j|}+\sum_{1\leq i<j<k\leq n}\frac{1}{|A_i\cup A_j\cup A_k|}-\cdots+\frac{(-1)^{n-1}}{|A_1\cup\cdots\cup A_n|}\\
&=\sum_{i=1}^n\frac{1}{|X|}-\sum_{1\leq i<j\leq n}\frac{1}{|X|}+\sum_{1\leq i<j<k\leq n}\frac{1}{|X|}-\cdots+\frac{(-1)^{n-1}}{|X|}\\
&=\frac{1}{|X|}\left(\binom{n}{1}-\binom{n}{2}+\binom{n}{3}-\ldots+(-1)^{n-1}\binom{n}{n}\right)\\
&=\frac{1}{|X|}\left(1-(1-1)^n\right)\\
&=\frac{1}{|X|}>0\tag{3}
\end{align*}

Other settings of $A_1,\ldots,A_n$ in between these extreme cases will give a result between the values of (2) and (3).

Question: It seems OPs expression could be some kind of measure of the scattering of $n$ subsets with $X=\bigcup_{i=1}^nA_i$. Maybe someone could point to related information?