# Homework Help: Proving the inclusion-exclusion principle

1. Sep 30, 2009

### cookiesyum

1. The problem statement, all variables and given/known data

Prove the general inclusion-exclusion formula.

2. Relevant equations

Inclusion-exclusion Formula:

P(C1 U C2 U...U Ck) = p1 - p2 + p3 - ... + (-1)(k+1)pk

where pi equals the sum of the probabilities of all possible intersections involving i sets.

3. The attempt at a solution

Assume that the formula holds for n sets. Then for n+1 sets...

P(union k=1 to n+1 of Ck) = P((union k=1 to n of Ck) union Cn+1) = P(union k=1 to n of Ck) + P(Cn+1) - P((union k=1 to n of Ck) intersect Cn+1) = P(union k=1 to n of Ck) + P(Cn+1) - P(union k=1 to n of (Ck intersect Cn+1)) = sum k=1 to n of P(Ck) + P(Cn+1)....

From there I don't know how to show the alternating pattern.

Last edited: Sep 30, 2009
2. Sep 30, 2009

### Office_Shredder

Staff Emeritus
You can use your inductive hypothesis to write out

P(union k=1 to n of Ck)

and

P((union k=1 to n of Ck) intersect Cn+1)

Using the fact that Cn+1 intersected with the union from 1 to n of Ck is the same as the union from 1 to n of (Ck intersected with Cn+1)

Share this great discussion with others via Reddit, Google+, Twitter, or Facebook