The purpose of this post is to record a small observation about the Principle of Inclusion and Exclusion that I haven’t seen before, but I’m sure must be well known.
Take the usual setup of a finite set containing subsets , , . Let . The inclusion-exclusion formula states that
Suppose that we truncate the sum in the inclusion-exclusion formula so that we only sum over sets of size at most . If denote the resulting integer then
for all odd . Thus the eventually provide successively better approximations to .
This result can be proved quite easily by adapting one of the standard proofs of the inclusion-exclusion formula. Let
where the sum is over all of size at most and is the indicator function of the set . Let . If belongs to at most of the sets then, as in the standard proof, if and otherwise. Suppose that belongs to exactly of the sets. Then
Let be the number of elements of which belong to exactly of the sets . We have
The difference between successive error terms is
this shows that the error terms are decreasing for .