Prove that the power set of an $n$-element set contains $2^n$ elements 
Theorem. Let $X$ denote an arbitrary set such that $|X|=n$. Then $|\mathcal P(X)|=2^n$.
Proof. The proof is by induction on the numbers of elements of $X$.
For the base case, suppose $|X|=0$. Clearly, $X=\emptyset$. But the empty set is the only subset of itself, so $|\mathcal P(X)|=1=2^0$.
Now, the induction step. Suppose $|X|=n$; by the induction hypothesis, we know that $|\mathcal P(X)|=2^n$. Let $Y$ be a set with $n+1$ elements, namely $Y=X\cup\{a\}$. There are two kinds of subsets of $Y$: those that include $a$ and those that don't. The first are exactly the subsets of $X$, and there are $2^n$ of them. The latter are sets of the form $Z\cup\{a\}$, where $Z\in\mathcal P(X)$; since there are $2^n$ possible choices for $Z$, there must be exactly $2^n$ subsets of $Y$ of which $a$ is an element. Therefore $|\mathcal P(Y)|=2^n+2^n=2^{n+1}$. $\square$

Image that replaced text.
From the above explanation, I don't understand why the set that contains $\{a\}$ will contain $2^{|n|}$ elements when it should clearly be $2^{|1|}$.
The construction of a new set $S$ is the union of the old set with cardinality $n$ and a new element $\{a\}$, therefore the set that does not contain $\{a\}$ still has cardinality $n$ and the set that contains $\{a\}$ is just $\{a\}$, one element.
Can someone please elucidate?

Alternative proof:
Represent a subset of $X$ as a binary number such that its $k^{th}$ bit is set if and only if the $k^{th}$ element is taken.
E.g., $\{a,b,c\}\to111$, $\{a,c\}\to101$, $\{c\}\to001$, ...
You can convince yourself that the two representations are equivalent, and that the second includes all binary numbers from $0$ to $2^{|X|}-1$.

Note that if you add an element, the subset of $X$ with signature $m$ generates two new subsets, with signatures $2m$ and $2m+1$.
