# 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 $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.