What is the proof that the total number of subsets of a set is $2^n$? [closed]

What is the proof that given a set of $n$ elements there are $2^n$ possible subsets (including the empty-set and the original set).

Suppose you want to choose a subset. For each element, you have two choices: either you put it in your subset, or you don't; and these choices are all independent.

Remark: this works also for the empty set. An empty set has exactly one subset, namely the empty set. And the fact that $2^0=1$ reflects the fact that there is only one way to pick no elements at all!

Here is a proof by induction on $n$. This proof assumes that we have defined $2^n$ by recursion as $2^0 = 1$ and $2^{n+1} = 2^n \cdot 2$.

This is true for $n=0$ because $\emptyset$ has exactly one subset, namely $\emptyset$ itself.

Now assume that the claim is true for sets with $n$ many elements. Given a set $Y$ with $n+1$ many elements, we can write $Y = X \cup \{p\}$ where $X$ is a set with $n$ many elements and $p \notin X$. There are $2^n$ many subsets $A \subset X$, and each subset $A \subset X$ gives rise to two subsets of $Y$, namely $A \cup \{p\}$ and $A$ itself. Moreover, every subset of $Y$ arises in this manner. Therefore the number of subsets of $Y$ is equal to $2^n \cdot 2$, which in turn is equal to $2^{n+1}$.

We must show that $${n\choose 0}+{n\choose 1}+{n\choose 2}+\cdots +{n\choose n}=2^n$$ is the number of subsets of an $n$-element set $S$ where $n\geq0$.

Every subset of $S$ is a $k$-subset of $S$ where $k=0,1,2,...,n$. We know that ${n\choose k}$ equals the number of $k$-subsets of S. Thus by the Addition Principle $${n\choose 0}+{n\choose 1}+{n\choose 2}+\cdots +{n\choose n}$$ equals the number of subsets to the set $S$. We can count the same thing by observing that each element of the set $S$ has two choices, either they are in a subset or they are not in a subset. Let $S=\{x_1,x_2,x_3,...,x_n\}$. So, $x_1$ is either in a subset or it is not in a subset, $x_2$ is either in a subset or it is not in a subset,..., $x_n$ is either in a subset or it is not in a subset. Thus by the Multiplication Principle there are $2^n$ ways we can form a subset of the set $S$. Hence ${n\choose 0}+{n\choose 1}+{n\choose 2}+\cdots +{n\choose n}=2^n$.

Another approach is to consider the Binomial Theorem $$(x+y)^n=\sum_{k=0}^n {n\choose k}x^{n-k}y^k.$$ Letting $x=1$ and $y=1$ we obtain$$2^n=\sum_{k=0}^n{n\choose k}.$$

Here is proof by binary numbers. A set of up to N items can be represented as a vector of binary digits. When a digit is 1, it indicates that the corresponding item is present. 0 means that it is absent.

In fact, this representation is used in computer programming as a way of representing sets which has good worst-case memory efficiency, as well as other attributes such as simplicity of implementation.

So for instance a set of 32 items can be represented as a string of 32 1's. And then we can represent subsets of these items, by flipping some of these 1's to 0's in various combinations.

All possible subsets are therefore, simply, all possible 32 bit numbers, and there are $2^{32}$ such numbers.

In other words, the count of subsets is related to the fact that set membership is a binary proposition: something is or is not an element of a set. Yes or no, true or false, one or zero.

\begin{align} \sum_{k=0}^n{n \choose k}=2^n \end{align} can be solved using proof by induction.

for n=1; it is true (put n=1);

for n=k; assume to be true. \begin{align} \sum_{k=0}^n{n \choose k}=2^n \end{align} for n=k+1; \begin{align} \sum_{k=0}^{n+1}{n+1 \choose k}=2^{n+1}\end{align} \begin{align} {n+1 \choose k}={n \choose k}+{n \choose k-1} \end{align}

substituting this equation leads to the final result.