Editing Boole's inequality (section)

=== Proof for odd K ===
Let <math> E = \bigcap_{i=1}^n B_i </math>, where <math> B_i \in \{A_i, A_i^c\} </math> for each <math> i = 1, \dots, n </math>. These such <math> E </math> partition the [[sample space]], and for each <math> E </math> and every <math> i </math>, <math> E </math> is either contained in <math> A_i </math> or disjoint from it.

If <math> E = \bigcap_{i=1}^n A_i^c </math>, then <math> E </math> contributes 0 to both sides of the inequality. 

Otherwise, assume <math> E </math> is contained in exactly <math> L </math> of the <math> A_i </math>. Then <math> E </math> contributes exactly <math> \mathbb{P}(E) </math> to the right side of the inequality, while it contributes 

:<math> \sum_{j=1}^K (-1)^{j-1} {L \choose j} \mathbb{P}(E) </math>

to the left side of the inequality. However, by [[Pascal's rule]], this is equal to

:<math> \sum_{j=1}^K (-1)^{j-1} \Big({L-1 \choose j-1} + {L-1 \choose j} \Big)\mathbb{P}(E) </math> 

which telescopes to 

:<math> \Big( 1 + {L-1 \choose K}\Big) \mathbb{P}(E) \geq \mathbb{P}(E) </math> 

Thus, the inequality holds for all events <math> E </math>, and so by summing over <math> E </math>, we obtain the desired inequality:

:<math> \sum_{j=1}^K (-1)^{j-1} S_j \geq \mathbb{P}\Big(\bigcup_{i=1}^n A_i\Big) </math> 

The proof for even <math> K </math> is nearly identical.<ref>{{cite book |first1=Santosh |last1=Venkatesh |title=The Theory of Probability |publisher=Cambridge University Press |year=2012 |isbn=978-0-534-24312-8 |pages=94–99 ,113–115 |url=http://www.cambridge.org/9781107024472 }}</ref>