Intereting Posts

Does having a codimension-1 embedding of a closed manifold $M^n \subset \mathbb{R}^{n+1}$ require $M$ to be orientable?
Derivative of the $f(x,y)=\min(x,y)$
Using Vieta's theorem for cubic equations to derive the cubic discriminant
Proof by strong induction combinatorics problem: $1(1!) + 2(2!) + 3(3!) + \dots + n(n!) = (n+1)! – 1$
Entire functions such that $f(z^{2})=f(z)^{2}$
Continuous function $f:\mathbb{R}\to\mathbb{R}$ such that $f(f(x)) = -x$?
numbers from $1$ to $2046$
General relationship between braid groups and mapping class groups
Liapunov's Inequality for $L_p$ spaces
A set $\,\{0,1\}^*$ is countable , but its subset $\,\{0,1\}^{\Bbb N}\,$ is uncountable?
Proving trigonometric equation $\cos(36^\circ) – \cos(72^\circ) = 1/2$
Is it possible to use regularization methods on the Harmonic Series?
Continued fraction for $c= \sum_{k=0}^\infty \frac 1{2^{2^k}} $ – is there a systematic expression?
Can we have an equation for any graph?
Operator: not closable!

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$.

- If $\sin x + \sin^2 x =1$ then find the value of $\cos^8 x + 2\cos^6 x + \cos^4 x$
- Proving $p\nmid \dbinom{p^rm}{p^r}$ where $p\nmid m$
- Expanding $\frac{\Gamma(n)}{\Gamma(n-k)}$ as a polynomial
- If $x+\frac1x=5$ find $x^5+\frac1{x^5}$.
- Given that$(3x-1)^7=a_7x^7+a_6x^6+a_5x^5+…+a_1x+a_0$, find $a_7+a_6+a_5+a_4+…+a_1+a_0$
- Can anybody help me with this logarithm problem?

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

- How is it, that $\sqrt{x^2}$ is not $ x$, but $|x|$?
- How to understand proof of a limit of a function?
- Find the centre of a circle passing through a known point and tangential to two known lines
- A.P. terms in a Quadratic equation.
- Why aren't the graphs of $\sin(\arcsin x)$ and $\arcsin(\sin x)$ the same?
- How to prove $\sum\limits_{r=0}^n \frac{(-1)^r}{r+1}\binom{n}{r} = \frac1{n+1}$?
- When the quadratic formula has square root of zero, how to proceed?
- Is there an analytic solution for the equation $\log_{2}{x}+\log_{3}{x}+\log_{4}{x}=1$?
- Why is $ (2+\sqrt{3})^n+(2-\sqrt{3})^n$ an integer?
- Prove that $\sum_{k=0}^n k^2{n \choose k} = {(n+n^2)2^{n-2}}$

Here is an analytic proof inspired by the one in

the answer to question #1343375 (thanks to kubek789 for the link!).

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.

**Note:** A remark in addition to the nice answer of @darijgrinberg.

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

+(-1)^{n-1 }\frac{1}{x_1+\ldots+x_n}>0 \qquad\qquad \tag{1}

\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 partitionLet’s assume the sets $A_i, 1\leq i \leq n$ form a

partitionof 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?

- Almost sure identity $F^{-1}(F(X))=X$ where $F$ is the CDF of $X$
- The 'sine and cosine theorem' – formulas for the sum and difference
- Economic price optimisation problem
- closed form expression of a hypergeometric sum
- Why is $b^x \overset{\mathrm{def}}{=} \sup \left\{ b^t \mid t \in \Bbb Q,\ t \le x \right\}$ for $b > 1$ a sensible definition?
- Book about technical and academic writing
- board game: 10 by 10 light bulbs, minimum switches to get all off?
- Integrating squared absolute value of a complex sequence
- Differentiability of $f(x) = \exp(-1/x^2), f(0) = 0$
- What is the distribution of orders of group elements?
- Solving for streamlines from numerical velocity field
- Prove that $ m_{a} \geq m_{g} \geq m_{h} $ using strict inequalities unless $ a = b $.
- If there is a unique left identity, then it is also a right identity
- Is any relation which contains only one ordered pair transitive?
- How do i visualize Cosets of a group