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

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