Bonferroni inequalities

Truncating the inclusion-exclusion principle after an odd number of terms gives an upper bound, and truncating after an even number gives a lower bound. In particular,

For the number $N$ of occurring events, write $S_j=\mathbb{E}\left(\genfrac{}{}{0ex}{}{N}{j}\right)$ and $T_m={\sum }_{r=0}^m(-1{)}^r(\genfrac{}{}{0ex}{}{k+r}{k})S_{k+r}$. Then odd truncations bound $\mathrm{Pr}(N=k)$ below and even truncations above. For each integer $N>k$, the truncated binomial sum equals $(-1{)}^m(\genfrac{}{}{0ex}{}{N}{k}\left)\right(\genfrac{}{}{0ex}{}{N-k-1}{m})$ when $m<N-k$, and is zero otherwise. Its sign proves the bounds on taking expectations. This is the exact-count version of the Bonferroni inequalities.