Let $A_{1}, A_{2}, \ldots, A_{n}$ be events in some probability space. State and prove the inclusion-exclusion formula for the probability $\mathbb{P}\left(\bigcup_{i=1}^{n} A_{i}\right)$. Show also that

$$\mathbb{P}\left(\bigcup_{i=1}^{n} A_{i}\right) \geqslant \sum_{i} \mathbb{P}\left(A_{i}\right)-\sum_{i<j} \mathbb{P}\left(A_{i} \cap A_{j}\right)$$

Suppose now that $n \geqslant 2$ and that whenever $i \neq j$ we have $\mathbb{P}\left(A_{i} \cap A_{j}\right) \leqslant 1 / n$. Show that there is a constant $c$ independent of $n$ such that $\sum_{i=1}^{n} \mathbb{P}\left(A_{i}\right) \leqslant c \sqrt{n}$.