Solution

ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2002/ia/paper-4/6f/a/solution

First, finite additivity of a set function gives , since . Put . Decomposing any subset into its singleton elements and using induction gives . Fix and let be the number of sets containing it. Its total coefficient in the alternating intersection sum is zero if , and otherwise is
by the binomial theorem. These are exactly the coefficients in . Summing against proves the required inclusion-exclusion principle for the additive set function, including signed weights.

New to topics? Read the docs here!