# Prove that inequality holds for all real number from $[0,1]$

There are given real numbers $a_1,a_2, ... , a_n \in [0,1]$

Prove that $\displaystyle \sum_{1\le i\le n} a_i \le 1+ \sum_{1\le i} \sum_{<j\le n} a_ia_j$

I have problem here because I can't find how to transfrom this formula to obtain what I want

• Should the first $a_{j}$ be $a_{i}$? – Vincent Apr 25 '14 at 14:25
• of course sorry for that – Gregor Apr 25 '14 at 14:33

This inequality has a probabilistic interpretation: if $\mathbb P$ is a probability measure and $A_i,1\leqslant i\leqslant n$ are events, then $$\mathbb P\left(\bigcup_{i=1}^nA_i\right)\geqslant \sum_{i=1}^n\mathbb P(A_i)-\sum_{1\leqslant i\lt j\leqslant n}\mathbb P(A_i\cap A_j).$$ This can be checked by induction. For $n=2$, there is equality, and if it's true for $n$, then $$\mathbb P\left(\bigcup_{i=1}^{n+1}A_i\right)=\mathbb P\left(\bigcup_{i=1}^nA_i\right)+\mathbb P(A_{n+1})-\mathbb P\left(A_{n+1}\cap \bigcup_{i=1}^nA_i\right)$$ and we conclude using the inequality $\mathbb P\left(A_{n+1}\cap \bigcup_{i=1}^nA_i\right)\leqslant \sum_{i=1}^n\mathbb P(A_{n+1}\cap A_i)$.
Then we use it when $A_i$ are independent event and we bound the probability of the union by $1$.
• See edit.${}{}{}$ – Davide Giraudo Apr 27 '14 at 8:36