Consider $ \scriptstyle n=1 $. For a set $ \scriptstyle S\textstyle\mid\scriptstyle\mid S\mid=1 $, there are two subsets: the empty set and $ \scriptstyle S $ itself. Indeed, there are $ \scriptstyle2^n=2^1=2 $ subsets.
Assume that for a finite but arbitrary $ \scriptstyle n=\mid S\scriptstyle\mid $, $ \scriptstyle\mid P(S)\mid=2^n $. Now consider adding an extra element to $ \scriptstyle S $ to create $ \scriptstyle S^' $. Obviously $ \scriptstyle P(S^') $ contains all subsets of $ \scriptstyle S $. However, for every subset of $ \scriptstyle S $, we may choose to either include or exclude the extra element. This constitutes 2 choices over $ \scriptstyle\mid P(S)\mid=2^n $ elements. So the total number of subsets of $ \scriptstyle S' $ is $ \scriptstyle2\cdot2^n=2^{n+1} $.
We have shown that $ \textstyle(\scriptstyle\mid S\mid=n\ \rightarrow\ \mid P(S)\mid=2^n\textstyle)\rightarrow(\scriptstyle\mid S^'\mid=n+1\ \rightarrow\ \mid P(S^')\mid=2^{n+1}\textstyle) $, so by induction, $ \scriptstyle\mid S\mid=n\ \rightarrow\ \mid P(S)\mid=2^n $ for all $ \scriptstyle n\in\mathbb{N} $. $ \scriptstyle\Box $
- --Nick Rupley 00:16, 22 January 2009 (UTC)
