Proof of PIE (Princple of Inclusion-Exclusion)


Most other people’s proofs are awful to look at/so long/so boring. Mine is an easily digestible paragraph

The main difference is that others prove the statement as a whole holds inductively (boo!) while I prove that each element is counted exactly once inductively (yay!)

PIE Statement

As a refresher, PIE states that

Given sets A_1,A_2,\dots,A_n,
$|A_1\cup A_2\cup \dots \cup A_n|=\sum\limits_{i=1}^{n} (-1)^{i}\sum\limits_{\text{sym}}|A_1\cap A_2\cap \dots \cap A_i|.$

PIE Proof

Here goes.

We claim that each element is counted once.

Say that some element X is in k sets. Without loss of generality, these sets are A_1,A_2,\dots,A_k.

We proceed by induction. This is obvious for k=1.

If this is true for k, we prove this is true for k+1. For every set of sets not containing A_{k+1} with size i, there is a set of sets containing A_{k+1} with size i+1. In PIE, the sum of how many times these sets are counted is 0. There is also one additional set of sets \{A_{k+1}\}, so X is counted exactly once.


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s