Proving number of subsets of a set size $n$ via induction I am trying to prove by induction that number of subsets of a set is equal to $2^n$. I start with the base case when n=1, for example, and the number of subsets is clearly 2. When we go to n=2, the number of subsets increases to 4, and I can see that this way: the empty subset is still there, the subset that has all elements is still there, the number of subsets that have only 1 element increases by 1, since we add another element, not sure about sets that have multiple elements in them (this is for $n \geq 3$; does it have to do with $\textrm{C}$ombinations? How can I write a mathematically rigorous inductive proof for this? Thanks!
 A: The usual trick is to assume the claim is true for $n$, and let $A$ be a set of $n+1$ elements.
Pick some $a\in A$, and let $A'=A\setminus\{a\}$. By the induction hypothesis $A'$ has exactly $2^n$ subsets.
For every subset of $A'$ we match a subset of $A$ with $a$ in it, by: $B\subseteq A'\mapsto B\cup\{a\}$. This is an injective function and since $a\notin A'$ so $B\neq B\cup\{a\}$.
Note that both $B$ and $B\cup\{a\}$ are subsets of $A$. In particular we have found $2\times 2^n$ subsets. We need to prove there are no others.
Let $C\subseteq A$ be some subset, if $a\notin C$ then we counted $C$ as a subset of $A'$, and if $a\in C$ then $C\setminus\{a\}$ was counted as a subset of $A'$ and was mapped to $C$ by adding $a$.
This shows that there are exactly $2\times 2^n = 2^{n+1}$ subsets of a set of size $n+1$.
A: You think of each subset as a binary string of 0's and 1's, where the $i^{th}$ character in the string is 0 if the $i^{th}$ element in the set is not in the subset.
So for your Inductive Hypothesis, you assume that there are $2^k$ unique binary strings of length $k$, so now you have to show that there are $2^{k+1}$ unique binary strings of length $k+1$.
So show that there are twice as many binary strings of length $k+1$ than length $k$.
(I leave this part up to you, since this is probably homework)
A: To show that the number of subsets of a set with $n$ elements is $2^{n}$, we shall use a combinatorial proof. We know that the binomial coefficient is given by
$\frac{n!}{k!(n-k)!}= {n \choose k}$, this in turn is the number of $\{A \subset \{1,..,n\}\}$, that is, the number of subsets $A$ of $\{1,...n\}$.
One of the properties of the binomial coefficient is the following: $(a+b)^{n}=\sum_{k=0}^{n} {n \choose k}a^{k}b^{n-k}$. Since we want to know $how$ many subsets $A$ of a set $\{1,...,n\}$ there are, we simply sum up the number of subsets $A$ of $\{1,...,n\}$, namely, $\sum_{k=0}^{n}{n \choose k}$ where $a=b=1$. Thus, $\sum_{k=0}^{n}{n\choose k}=(1+1)^{n}=2^{n}$.
