Past exam of the mathematics course of the University of Cambridge / 2020 / ia / Paper 1 / 11F / Solution

For events $A_1,\dots ,A_n$, the probabilistic inclusion-exclusion principle isTo prove it, fix an outcome lying in exactly $r$ events. Its total coefficient on the right isby the binomial theorem; outcomes in no event contribute zero. Taking expectations of this pointwise indicator identity proves the formula. Truncating after the pair terms gives the Bonferroni inequalities

For the final bound, let $X={\sum }_i{1}_{A_i}$ and $S=\mathbb{E}X={\sum }_i\mathbb{P}(A_i)$. The intersection assumption givesThe Cauchy-Schwarz inequality applied to $X{1}_{X>0}$ yields $S^2\le \mathbb{E}[X^2]\mathbb{P}(X>0)\le S+n-1$. Thereforeso the required universal constant may be taken as $\boxed{c=2}$. This is a second moment method estimate.