How to prove this identity in a combinatorial way? \begin{equation}
\sum_{k=0}^{n}\left(\begin{array}{c}{2 n+1} \\ {k}\end{array}\right)=2^{2 n}
\end{equation}
I managed to prove it in an algebric way but not in combinatorial one.
Thanks!
Not a duplicate.
 A: Let $S=\{1,2,\dots,2n+1\}$.
We wish to prove that $\mathcal{A}=\{A\subseteq S:~|A|\leq n\}$ is in bijection with $\mathcal{B}=\{B\subseteq S:~2n+1\notin B\}$.  It is clear that $|\mathcal{A}|$ is counted by the LHS of your identity while $|\mathcal{B}|$ is counted by the RHS of your identity.
Consider the function $f:\mathcal{A}\to\mathcal{B}$ given by:
$$f(A) = \begin{cases} A&\text{if }2n+1\notin A\\ S\setminus A&\text{if }2n+1\in A\end{cases}$$
Notice that if $2n+1\notin A$ then $|f(A)|=|A|\leq n$.  On the other hand, if $2n+1\in A$ then $|f(A)|=|S\setminus A| = 2n+1-|A|\geq n+1$
Suppose then that $f(A_1) = f(A_2)$.  This implies that either $2n+1$ is in both $A_1$ and $A_2$ or it is in neither.  In the first case, that would imply that $A_1=A_2$.  Otherwise, that would imply that $S\setminus A_1=S\setminus A_2$ which in turn implies that $A_1=A_2$.  Therefore, the function is injective.
For surjectivity, consider an arbitrary subset $B$ not containing $2n+1$ of $S$.  In the event that $|B|\leq n$ then $B\in\mathcal{A}$ and $f(B)=B$.  Otherwise, if $|B|\geq n+1$ we have $S\setminus B\in \mathcal{A}$ and that $f(S\setminus B)=B$.
Thus the function is a bijection and the identity is proven.
