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

Question

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!

Answer 1

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.

Answer 2

$$ \sum_{k=0}^n {n \choose k} =\sum_{k=0}^n {n \choose k}\cdot 1^k\cdot 1^{n-k}= (1+1)^n = 2^n$$

Answer 3

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.