Q:

How many subsets are there of a set consisting of $n$ elements?

I understand that there should be $\sum_{k=0}^n {n \choose k}$ subsets but I don't understand how that expression simplifies to $(1+1)^n$ or $2^n$
Namely, I don't understand this equation: 
$$ \sum_{k=0}^n {n \choose k} = (1+1)^n = 2^n$$
Please explain in detail, thanks! 

A:

The binomial theorem states that
$$(x+y)^n=\sum_{k=0}^n {n \choose k}x^{n-k}y^k$$
for a natural number $n$. Using that equation, from right to left,
$$\begin{align}
\sum_{k=0}^n {n \choose k} &= \sum_{k=0}^n {n \choose k}1^{n-k}1^k \\[2 ex]
 &= (1+1)^n \\[2 ex]
 &= 2^n
\end{align}$$
You see that I used the binomial theorem with $x=y=1$ and the fact that $1^m=1$ for any natural number $m$. The binomial theorem itself is proved by mathematical induction, and this special case can be proved this way as well.

A:

I like the combinatorial argument:
When building a subset, we are choosing among $n$ elements. Each element may either be in the subset, or not in the subset. Thus there are $2^n$ ways to build a subset.

