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

Question

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.

Answer 1

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

Answer 2

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!

Answer 3

$$\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.

Answer 4

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*}