We prove by induction on .

Base case. For the empty set has exactly one subset, itself.

Inductive step. Suppose the result holds for some , and let be a set of size . Pick some element , and let . Then has size , and by the inductive hypothesis has exactly subsets.

Each subset of either includes or excludes : taking each subset of and either adding or not gives exactly two choices per subset of , leading to subsets of . Hence, by induction, the result holds for all .