Proving $\sum_{k=0}^n \binom{n}{k} = 2^n$ combinatorially?

Question

I am trying to prove the basic fact that

$$\sum_{k=0}^n \binom{n}{k} = 2^n$$

I can use the binomial theorem, simply setting $x = y = 1$, but how can I prove this combinatorially?

Thanks.

Answer 1

Okay. So you have a collection of $n$ objects and you want to count the number of ways to select a subset of them. First off note that for each of the $n$ objects, either it is in the set or it isn't. Hence, this way of counting gives $2^n$. The other way is to count the number of ways to select a subset of size $k$ for each $0\leq k\leq n$, and then add them up. This gives the left hand expression.

Answer 2

Let $\mathcal P$ the set af all subsets of $E=\{1,2,...,n\}$ an $\mathcal P_k$ the set of all subsets of $E$ having $k$ elements. then $\{\mathcal P_0, \cdots,\mathcal P_n\}$ is a partition of $\mathcal P$.

Since $$\text{card}(\mathcal P)=2^n$$ and for all $k \in \{0,1,\cdots,n\}$: $$\text{card}(\mathcal P_k)=\binom{n}{k}$$ and $$\text{card}(\mathcal P)=\sum_{k=0}^n \text{card}(\mathcal P_k)$$ we get the formula to proof.

Answer 3

You are given a set $S$ of $n$ objects and you are tasked with finding the number of subsets in the set.

There are two ways of counting the number of subsets. The first one is the evident one of $|S|=2^n$ (if you don't know the proof, I can show it to you).

The second method of computing is finding the number of subsets of a fixed cardinality $0\leq k\leq n$, and then summing them all up from $k=0$ to $k=n$. By the definition of the binomial coefficients, there are $\binom{n}{k}$ ways of choosing $k$ objects in our set, and hence $\displaystyle |S|=\sum_{k=0}^n \binom{n}{k}$.

And so, we get: $\displaystyle 2^n=|S|=\sum_{k=0}^n \binom{n}{k}$