Prove by induction on n: If a set A has n elements, its power set has 2^n elements.
*Given a set A, the power set of A is the set of all subsets of A
P(k)
The power of a set with k elements is $\displaystyle 2^k$
P(k+1)
The power of a set with k+1 elements is $\displaystyle 2^{k+1}$
Show that P(k+1) must be true if P(k) is true.
If a set of k elements has a power of $\displaystyle 2^k$
then an added element will form $\displaystyle 2^k$ new subsets as it can be placed with all $\displaystyle 2^k$ existing subsets.
Therefore a set of k+1 elements has a power of $\displaystyle (2)2^k$ if a set of k elements has power $\displaystyle 2^k.$
Finally prove for the base case.
This proof turns on a simple fact: $\displaystyle 2^n+2^n=2(2^n)=2^{n+1}.$
Any subset of $\displaystyle \{1,2,\cdots,n\}$ is a subset of $\displaystyle \{1,2,\cdots,n,n+1\}.$
So by uniting any subset of $\displaystyle \{1,2,\cdots,n\}$ with $\displaystyle \{n+1}\}$ we get a subset of $\displaystyle \{1,2,\cdots,n+1\}$.