3
$\begingroup$

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

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

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

$\endgroup$
  • $\begingroup$ can you show how to check this inequality by induction? $\endgroup$ – Gregor Apr 26 '14 at 19:05
  • $\begingroup$ See edit.${}{}{}$ $\endgroup$ – Davide Giraudo Apr 27 '14 at 8:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.