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?
 A: 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$.
A: Here is an another, combinatorial proof. Let $X$ be a set with $n$ elements. To form a subset of $X$, we go over each element of $X$ and exercise a choice of whether or not to include in the subset. Every sequence of choices gives a different subset.
Since for every element, there are 2 choices, for $n$ elements, there are $2 \times 2 \times ...$ $n$ times, choices.
Therefore, there are $2^n$ distinct subsets of $X$.
A: You misread the proof. Since set $X$ has $n$ elements, the induction hypothesis tells us that $|\mathcal{P}(X)| = 2^n$.  The set $Y = X \cup \{a\}$ has $n + 1$ elements.  It subsets are either subsets of $X$, of which there are $2^n$ by the induction hypothesis, or the union of a subset $Z$ of $X$ with $\{a\}$.  By the induction hypothesis, there are $2^n$ subsets $Z$ of $X$.  Hence, there are $2^n$ subsets of the form $Z \cup \{a\}$ of the set $Y$.  Hence, $Y$ has $2^n$ subsets that do not contain $a$ and $2^n$ subsets that do contain $a$ for a total of $2^n + 2^n = 2 \cdot 2^n = 2^{n + 1}$ subsets of $Y$, which is what the author wants to show.
A: Suppose you've already shown that $X=\{1,2\}$ has $2^2=4$ subsets, namely ${\cal P}(X)=\{\emptyset,\{1\},\{2\},X\}$.  Now you add a new element $a=3$ to get $Y=X\cup \{a\}=\{1,2,3\}$.  The four subsets of $X$ are also subsets of $Y$, but you get new subsets - those which contain $a$, e.g. $\{1,3\}$.  But each of these is one of the ones you already had together with the new $a$, e.g. $\{1,3\}$ is $\{1\} \cup \{3\}$.
So, the new ones are $\emptyset \cup \{3\}$, $\{1\} \cup \{3\}$, $\{2\} \cup \{3\}$, and $X \cup \{3\}$ and those are exactly as much as you already had - four of them.  Which implies that ${\cal P}(Y)$ has twice as much elements (the old ones and the new ones) as ${\cal P}(X)$, so $2\times2^2=2^3=8$.
$$
\begin{array}{|c|c|}
\hline
\text{Subsets of }X&\text{New subsets}\\
\hline
\emptyset&\{3\}\\
\hline
\{1\}&\{1,3\}\\
\hline
\{2\}&\{2,3\}\\
\hline
X&Y\\
\hline
\end{array}
$$
A: I will prove the claim by induction. First suppose $|A|=1$. That is, $A=\{a_1\}$. Thus, $P(A) =\{ \{a\}, \{ \emptyset \} \}$. So, it can be concluded that $|A|=2^1=2$. My inductive hypothesis is that $|A|=n$ and $|P(A)|=2^n$. Now let's consider $A'$, where $A'$ is $A$ with one new element added, call it $a_{n+1}$. That is to say $A'= \{a_1,a_2,a_3,\dots,a_{n+1} \}$. When considering $P(A')$ two types of sets arise, those containing $a_{n+1}$ and those that do not. Allow $B_i$ to represent any particular member of $P(A)$. Notice that $|P(A')|=|P(A)|+|B_k \cup\{a_{n+1}\}|$,  for all $k\in \mathbb{N}$ satisfying $1\leq k\leq 2^n$. Therefore $|P(A')|=2^n+2^n=2\cdot 2^n=2^{n+1}$. $\square$ 
A: Here is another one that uses the Binomial Theorem.
Take, for example, the set $A = \{1, 2, 3, 4\}$
Then, $P(A) = \{∅, \{1\}, \{2\}, \{3\}, \{4\}, \{1, 2\}, \{1, 3\}, \{2, 3\}, \{2, 4\}, \{3, 4\}, \{4, 1\}, \{1, 2, 3\}, \{2, 3, 4\}, \{3, 4, 1\}, \{4, 1, 2\}, \{1, 2, 3, 4\}\}$
In $P(A)$, see that the number of subsets with cardinality 0 is 1, there are 4 subsets with cardinality 1, 6 with cardinality 2, then 4 again with 3 and then 1 more with cardinality 4. $\pmb{1-4-6-4-1}$; $16$ total. Note that these are the coefficients of the terms when you expand the binomial theorem (binomial coefficients) with $n=4$.
Now we want the sum of these numbers. This is can be easily achieved by replacing $x=y=1$ in the binomial formula where $n$ is the cardinality of set A and the formula follows from there.

Why the pattern appears is very simple. Let $n$ be $|A|$. You want to fill subsets of cardinalities $0, 1, \cdots,\ n$. You have n elements to choose from. So to fill the first subset with cardinality 0, you use $\binom{n}{0}$, for the second with cardinality 1 we use $\binom{n}{1}$ and so on.
