268
Sets, Combinatorics, and Probability
For n = 3, this gives 0 A 1 d A 2 0 (i = 1, j = 2), 0 A 1 d A 3 0 (i = 1, j = 3), and 0 A 2 d A 3 0
(i = 2, j = 3). This agrees with Equation (3), where A 1 = A, A 2 = B, and A 3 = C.
To prove the general form of the principle of inclusion and exclusion, we use
mathematical induction. Although the idea of the proof is straightforward, the
notation is rather messy. The base case, n = 2, is just Equation (2). We assume
that Equation (4) is true for n = k and show that it is true for n = k + 1. We write
0 A 1 c c c A k + 1 0
= 0 (A 1 c c c A k ) c A k + 1 0
= 0 (A 1 c c c A k ) 0 + 0 A k + 1 0
− 0 (A 1 c c c A k ) d A k + 1 0
(by Equation (2))
= ∙
1≤i≤k
0 A i 0 − ∙
1≤i 0 A i d A j 0 +
∙
1≤i 0 A i d A j d A m 0
− c + (−1)
k+1
0 A 1 d c d A k 0 + 0 A k + 1 0
− 0 (A 1 d A k + 1 ) c c c (A k d A k + 1 ) 0
(by the inductive hypothesis and the distributive property)
= ∙
1≤i≤k+1
0 A i 0 − ∙
1≤i 0 A i d A j 0 +
∙
1≤i 0 A i d A j d A m 0
− c + (−1)
k+1
0 A 1 d c d A k 0
− a ∙
1≤i≤k
0 A i d A k + 1 0 − ∙
1≤i 0 A i d A j d A k + 1 0 + c +
+ (−1)
k
∙
1≤i 0 (A i d A k + 1 ) d (A j d A k + 1 ) d c d (A m d A k + 1 ) 0
+ (−1)
k+1
0 A 1 d c d A k + 1 0b
(by combining terms ➀ from above and using the inductive hypothesis on the k sets
A 1 d A k + 1 , A 2 d A k + 1 , … , A k d A k + 1 )
= ∙
1≤i≤k+1
0 A i 0 −
∙
1≤i 0 A i d A j 0 +
∙
1≤i 0 A i d A j d A m 0
− c − (−1)
k+1
0 A 1 d c d A k + 1 0
(by combining like-numbered terms from above)
= ∙
1≤i≤k+1
0 A i 0 −
∙
1≤i 0 A i d A j 0 +
∙
1≤i 0 A i d A j d A m 0
− c + (−1)
k+2
0 A 1 d c d A k + 1 0
This completes the proof of Equation (4). A different proof of the principle of inclusion and exclusion can be found in Exercise 23 of Section 4.5.
➀
➀
➁
➂
➁
➂
➃
('''''''''')''''''''''*
k − 1 terms
➃