MA2102
Probability and Statistics
Lecture-3
Inclusion-Exclusion
Question: How many numbers between between that are divisible by or
let =all numbers from that are divisible by then
let =all numbers from that are divisible by then
and will contains all numbers between that are divisible by or , so can we apply Sum rule? no, because
would be wrong, and count more because some numbers got over counted, but we can fix it. Because we can see what exactly getting over counted, numbers in counted once in and once in means they got counted twice but they supposed to be counted only once, so the fix is the following.
(this is the idea, include and exclude in controlled way)
( )
Similarly if we have three finite sets then
Thoerem(Principle of Inclusion and Exclusion): Let be finite sets. Then
proof: by induction on n(you try using base case for n=2)