Proving the inclusion-exclusion principle

[cookiesyum]

Homework Statement

Prove the general inclusion-exclusion formula.

Homework Equations

Inclusion-exclusion Formula:

P(C₁ U C₂ U...U C_k) = p₁ - p₂ + p₃ - ... + (-1)^(k+1)p_k

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

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.

 

[Office_Shredder]

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.

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 C_n+1 intersected with the union from 1 to n of C_k is the same as the union from 1 to n of (C_k intersected with C_n+1)