Another proof is by induction on n.

The base case is for n = 0. That means S = {}. So the claim to be shown is:

\\[|2^{\lbrace \rbrace}| = 2^{|\lbrace \rbrace|} \\]

\\(2^{\lbrace \rbrace\}\\) is all subsets of \\(\lbrace \rbrace\\), which just contains one member \\(\lbrace \rbrace\\). So the left side equals 1. On the right, since \\(|\lbrace \rbrace|\\) equals 0, we also get 1.

For the induction step, we'll show that increasing \\(S\\) by one element doubles the size of \\(2^S\\).

Let \\(S' = S \cup \lbrace x \rbrace\\). To each subset \\(A\\) of \\(S\\) we can associate a pair of subsets of \\(S'\\) -- \\(A\\) itself, and \\(A \cup \lbrace x \rbrace\\). And this mapping is _unique_, in that every subset of \\(A'\\) gets hit by the mapping, and gets hit only once. So the number of subsets of \\(A'\\) is exactly twice the number of subsets of \\(A\\).

The base case is for n = 0. That means S = {}. So the claim to be shown is:

\\[|2^{\lbrace \rbrace}| = 2^{|\lbrace \rbrace|} \\]

\\(2^{\lbrace \rbrace\}\\) is all subsets of \\(\lbrace \rbrace\\), which just contains one member \\(\lbrace \rbrace\\). So the left side equals 1. On the right, since \\(|\lbrace \rbrace|\\) equals 0, we also get 1.

For the induction step, we'll show that increasing \\(S\\) by one element doubles the size of \\(2^S\\).

Let \\(S' = S \cup \lbrace x \rbrace\\). To each subset \\(A\\) of \\(S\\) we can associate a pair of subsets of \\(S'\\) -- \\(A\\) itself, and \\(A \cup \lbrace x \rbrace\\). And this mapping is _unique_, in that every subset of \\(A'\\) gets hit by the mapping, and gets hit only once. So the number of subsets of \\(A'\\) is exactly twice the number of subsets of \\(A\\).