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

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!

-

## marked as duplicate by Lord_Farin, egreg, user1337, Asaf Karagila, azimutNov 28 '13 at 15:41

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

-
thanks this makes a lot of sense. A nice way to put words in math! And a nice trick with $C$ too. I can accept the answer in 4 minutes. – confused Jun 12 '11 at 6:28
@confused: I gave this proof when I TA'd an introductory course on set theory last semester, it is a course that most of the proofs use words rather than symbols and numbers. I like that in mathematics. :-) – Asaf Karagila Jun 12 '11 at 7:59
a nice proof. @confused i wonder whether that 4 minutes are still counting.. – Anubis Jan 19 '13 at 5:43
@Anubis: I don't get that comment... – Asaf Karagila Jan 19 '13 at 8:34

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)

-
Thanks a lot Nicolas (this is not homework, just me solving a Real Analysis text over summer). This is quite elegant too, I think, since we just add another 0/1 at the end of a string by adding another element, and thus go from $2^n$ to $2^{n+1}$ -- clever! – confused Jun 12 '11 at 6:29

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

-
The binomial coefficient ${n \choose k}$ is related to the number of set of size $k$...You forgot about $k$. – user37238 Oct 3 '13 at 8:17
And this is not a proof based on induction. – user37238 Oct 3 '13 at 8:23