Prove this using counting techniques: $\sum_{k=0}^{n}{\binom{2n+1}k} = 2^{2n}$ I recently came across a question while studying for an exam. I haven't been able to solve it. We had to prove:
$$\sum_{k=0}^{n}{2n+1\choose k} = 2^{2n}$$
We had to use counting techniques. This was my attempt
Let S be the set of all subsets of [1....2n]. We know that the size of S is $2^{2n}$
Another way of counting the subsets of [1....2n] is ?????
...
Therefore, since we've used two different methods to count the same thing, then 
$$\sum_{k=0}^{n}{2n+1\choose k} = 2^{2n}$$
My problem is, I can't think of a second way to count the subsets such that it equals the summation. Am I on the right track here, or is there another set of objects I can count to make the proof easier?
Thanks for the help.
 A: 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!
A: $$\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.
A: The subsets of $\{1,\ldots,2n+1\}$ come in pairs of complements. Exactly one member of each such pair has up to $n$ elements.
A: Here is a way to see that
$$
\sum_{k=0}^{n} {2n+1 \choose k} = 2^{2n},
$$
by a counting argument which counts the number of subsets of $\{1, \ldots, 2n\}$ rather than half the number of subsets of $\{1, \ldots, 2n, 2n+1\}$. Essentially to count the subsets of $\{1, \ldots, 2n\}$, we break the subsets into whether or not their size is at most $n$. 
Now to choose a subset, $B$, of $\{1, \ldots, n\}$, for some $0 \leq k \leq n$, we choose $k$ elements of $\{\star, 1, 2, \ldots, 2n\}$ getting a subset $A$. If $\star$ is not in $A$, then set $B=A$. If $\star$ is in $A$, then set $B=\{1, \ldots, 2n\} \setminus A$. Now the number of ways to choose our set $A$ is precisely 
$$
\sum_{k=0}^{n} {2n+1 \choose k}.
$$
What remains is to show a 1-1 correspondence between the sets $A$ and subsets of $\{1, 2, \ldots, 2n\}$. 
First, let us show that the correspondence between sets $A$ and subsets $B$ is onto. If $B$ is a subset of $\{1, \ldots, 2n\}$, then if $|B| \leq n$, we can let $A=B$; but if $|B| \geq n+1$, then we set $A=\{\star\} \cup \left( \{1, \ldots, 2n\}\setminus B\right)$ [now $|A| = 1+2n-|B| \leq n.$] Either way, this $A$ would give rise to our subset $B$. 
Conversely, let us show that this correspondence is injective. Suppose $A$ and $A'$ both correspond to subset $B=B'$. Now if either $A$ and $A'$ both contain $\star$ or $A$ and $A'$ both do not contain $\star$, then clearly we must have $A=A'$. Suppose $A$ contains $\star$ but $A'$ does not. However,
\begin{align*}
|B| = 2n-(|A|-1) = n+1 +(n-|A|) &\geq n+1 \\&> n \geq |A'|=|B'|.
\end{align*}
