Proving number of subsets of a set size $n$ via induction [duplicate]

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$.

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)

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}$.