Proof of intersection formula

gistfile1.tex

|\intersection_{i=(1..k)} s_i| = -\sum_{b=(0..2^k - 1)} (-1)^{|b|} |\union_i (s_i)^(b_i)|

where s_i^1 = s_i, and s_i^0 = {} (the empty set).
|b| is the number of 1 values in the binary representation.

Proof, base case = k = 2 (which is to say there is just s_1, s_2).
|s_1 n s_2| = -|{}| + |s_1| + |s_2| - |s_1 u s_2|
which is clearly true because |{}| = 0, and the fact that
|s_1| + |s_2| = |s_1 n s_2| + |s_1 u s_2|

Assume it is true for k, now let's look at k+1.
|s_1 n s_2 n... s_k n s_{k+1}|
= |(s_1 n s_2 n... s_k) n s_{k+1}|
= |s_1 n s_2 n... s_k| + |s_{k+1}| - |(s_1 n s_2 n... s_k) u s_{k+1}|
= |s_1 n s_2 n... s_k| + |s_{k+1}| - |(s_1 u s_{k+1}) n (s_2 u s_{k+1}) n .. (s_k u s_{k+1})}

The above only involves intersections of size k, and we already have the formula for intersections of size k. The first set of intersections is given by the formula above. The second term is a singleton |s_{k+1}|.  The last term we need to investigate, but note the formula applies with s_i' = s_i u s_{k+1}

|(s_1 u s_{k+1}) n (s_2 u s_{k+1}) n .. (s_k u s_{k+1})}|
= |s_1' n s_2' n... s_k'|
-\sum_{b=(0..2^k - 1)} (-1)^{|b|} |\union_i (s_i')^(b_i)|

But note that \union_i (s_i')^(b_i) = s_{k+1} \union_i (s_i)^(b_i) = \union_i (s_i)^(1|b_i)

where (1|b_i) denotes that set k+1 is always present and has bit value 1.

Note that (-1)^{|b|} = -(-1)^{|1b|} because |1b| = |b| + 1.  Since summing over all values b 0 to 2^{k} - 1 and prepending a 1 is the same as summing over all values 2^k to 2{k+1} - 1, we have proved the result.