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

where .

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

where

The difference between successive error terms is

Since

this shows that the error terms are decreasing for .