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!)
As a refresher, PIE states that
We claim that each element is counted once.
Say that some element is in sets. Without loss of generality, these sets are
We proceed by induction. This is obvious for
If this is true for we prove this is true for For every set of sets not containing with size there is a set of sets containing with size In PIE, the sum of how many times these sets are counted is There is also one additional set of sets so is counted exactly once.