Why is $2^n$ the maximum number of subsets of a set of size $n$? There is a set with $n$ elements. Why is the maximum number of subsets that can be formed out of it $2^n$?
 A: 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}.$$
A: Ross Belgram's method is a classic way to do it. Here's a faster way. 
Consider a subset of the set $S=\{a_1,a_2,\cdots,a_n\}$, which has $n$ elements. To create a subset, which may be empty, we can go through each of the elements in the set $S$ and either put it in the subset or not put it in the subset. 
That is, we have two choices for a given $a_k$: in the subset or not. So, if we have $2$ choices for each of the $n$ elements, the total number of subsets possible is $$ \underbrace {2 \cdot 2 \cdots 2}_{n \, \text{checks}} = 2^n. $$This is sometimes known as committee-forming since it is analogous to the situation where we want to form a committee of arbitrary size, given $n$ people. And, so for each of the people, you can either put the person in the committee or not put him in the committee, thus giving $2^n$ possible committees. 
$ \blacksquare $ 
A: Given the number of answer given so far that mention binomial coefficients, I just want to say you don't need them for this problem. Repeating the comment by Daniel Fischer, all you need to know is that is subset $S$ is determined by telling for each of the $n$ elements $x$ whether $x\in S$ or $x\notin S$. That gives $2$ possibilities for $x$, and repetaing this for every $x$ gives $2^n$ possibilities. Once all those choices are fixed, the subset $S$ is completely determined. There are precisely $2^n$ subsets.
A: If we choose  $r$ elements (where $0\le r\le n$) of $n$ elements to form subsets, there can be $\binom nr$ combinations
We know $$\sum_{0\le r\le n}\binom nr=(1+1)^n$$
