Proof of PIE (Princple of Inclusion-Exclusion)

Introduction

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 $\latex A_1,A_2,\dots,A_n,$
$$\latex |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 $\latex X$ is in $\latex k$ sets. Without loss of generality, these sets are $\latex A_1,A_2,\dots,A_k.$

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

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

 

Leave a Reply

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

WordPress.com Logo

You are commenting using your WordPress.com 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