Aquí es una manera de ver que
$$
\sum_{k=0}^{n} {2n+1 \elegir k} = 2^{2n},
$$
por un recuento de argumento que cuenta el número de subconjuntos de a $\{1, \ldots, 2n\}$ más de la mitad el número de subconjuntos de a $\{1, \ldots, 2n, 2n+1\}$. Esencialmente a contar los subconjuntos de a $\{1, \ldots, 2n\}$, rompemos los subconjuntos de si o no su tamaño es en la mayoría de las $n$.
Ahora a elegir un subconjunto, $B$$\{1, \ldots, n\}$, para algunas de las $0 \leq k \leq n$, elegimos $k$ elementos de $\{\star, 1, 2, \ldots, 2n\}$ obtener un subconjunto $A$. Si $\star$ no $A$, a continuación, establezca $B=A$. Si $\star$$A$, a continuación, establezca $B=\{1, \ldots, 2n\} \setminus A$. Ahora el número de formas de elegir nuestro set $A$ es precisamente
$$
\sum_{k=0}^{n} {2n+1 \elegir k}.
$$
Lo que queda es mostrar 1-1 de la correspondencia entre los conjuntos de $A$ y los subconjuntos de a $\{1, 2, \ldots, 2n\}$.
En primer lugar, vamos a mostrar que la correspondencia entre los conjuntos de $A$ y subconjuntos $B$ es sobre. Si $B$ es un subconjunto de a $\{1, \ldots, 2n\}$, entonces si $|B| \leq n$, podemos dejar que la $A=B$; pero si $|B| \geq n+1$, entonces nos pusimos $A=\{\star\} \cup \left( \{1, \ldots, 2n\}\setminus B\right)$ [ahora $|A| = 1+2n-|B| \leq n.$] de cualquier manera, esto $A$ daría lugar a nuestro subconjunto $B$.
Por el contrario, vamos a mostrar que esta correspondencia es inyectiva. Supongamos $A$ $A'$ corresponden ambos a subconjunto $B=B'$. Ahora si $A$ $A'$ ambos contienen $\star$ o $A$ $A'$ tanto no contienen $\star$, entonces es claro que debemos tener $A=A'$. Supongamos $A$ contiene $\star$ pero $A'$ no. Sin embargo,
\begin{align*}
|B| = 2n-(|A|-1) = n+1 +(n-|A|) &\geq n+1 \\&> n \geq |A'|=|B'|.
\end{align*}
