Prove this using counting techniques: $\sum_{k=0}^{n}{\binom{2n+1}k} = 2^{2n}$

The subsets of $\{1,\ldots,2n+1\}$ come in pairs of complements. Exactly one member of each such pair has up to $n$ elements.


We have to consider the set $\{1,2,3,...,2n+1\}$. There are $2^{2n+1}$ subsets here.

However, another way to look at this is that we can choose $k$ numbers from the set of $2n+1$ elements, which is ${2n+1 \choose k}$. We sum this from $k=0$ to $k=2n+1$, giving us: $$\sum_{k=0}^{2n+1} {2n+1 \choose k}=2^{2n+1}$$ Now, remember that: $${2n+1 \choose k}={2n+1 \choose 2n+1-k}$$ This means ${2n+1 \choose 2n+1}$ is a duplicate of ${2n+1 \choose 0}$, ${2n+1 \choose 2n}$ is a duplicate of ${2n+1 \choose 1}$, ${2n+1 \choose 2n-1}$ is a duplicate of ${2n+1 \choose 2}$, ..., and ${2n+1 \choose n+1}$ is a duplicate of ${2n+1 \choose n}$. Therefore, we can sum from $k=0$ to $k=n$ and then multiply that by $2$ to account for the duplicates: $$2\sum_{k=0}^{n} {2n+1 \choose k}=2^{2n+1}$$ Hopefully, you can take it from here. Good luck!


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

$$2^{2n+1}=\sum_{k=0}^{2n+1}{2n+1\choose k}=\sum_{k=0}^{n}{2n+1\choose k}+\sum_{k=n+1}^{2n+1}{2n+1\choose k}=2\sum_{k=0}^{n}{2n+1\choose k}$$

$$\implies 2^{2n+1}=2\sum_{k=0}^{n}{2n+1\choose k}$$

which implies the result given.

An interpretation of this is that a randomly selected subset of $\{1,\cdots,2n+1\}$ is equally likely to contain $\le n$ or $>n$ elements.