<s>[INST] Prove $2^{2n} = \sum_{k=0}^{n}\binom{2n+1}{k}$ I'm trying to prove the following equation above. So far I have:
\begin{align}
2^{2n} &= (1+1)^{2n}\\
&= \sum_{k=0}^{2n}\binom{2n}{k}1^k1^{n-k} = \sum_{k=0}^{2n}\binom{2n}{k} & \text{(By the Binomial Theorem)}
\end{align}
I know I have to use the following identity somehow:
$$\binom{n+1}{k} = \binom{n}{k-1} + \binom{n}{k}$$
How do I split my summation to get what I'm looking for? Thanks!
EDIT: HERE IS MY SOLUTION
\begin{align*}
2^{2n} &= (1+1)^{2n}\\
&= \sum_{k=0}^{2n}\binom{2n}{k}1^k1^{2n-k} & \text{(By the Binomial Theorem)}\\
&= \sum_{k=0}^{n}\binom{2n}{k} + \sum_{k=n+1}^{2n}\binom{2n}{k}\\
&= \sum_{k=0}^{n}\binom{2n}{k} + \sum_{k=n+1}^{2n}\binom{2n}{2n-k} & \text{(Binomial Symmetry)}\\
&= \sum_{k=0}^{n}\binom{2n}{k} + \sum_{k=0}^{n-1}\binom{2n}{k}\\
&= \sum_{k=0}^{n}\binom{2n}{k} + \sum_{k=1}^{n}\binom{2n}{k-1}\\
&= \binom{2n}{0} + \sum_{k=1}^{n}\binom{2n}{k} + \sum_{k=1}^{n}\binom{2n}{k-1}\\
&= \binom{2n}{0} + \sum_{k=1}^{n}\binom{2n+1}{k} & \text{(By Identity listed above)}\\
&= \sum_{k=0}^{n}\binom{2n+1}{k}
\end{align*}
 [/INST] $$\sum_{k=0}^{n}\binom{2n+1}{k}=\frac{1}{2}\sum_{k=0}^{2n+1}\binom{2n+1}{k}=\frac{2^{2n+1}}{2}=2^{2n}$$
Using the relation $$\binom{2n+1}{k}=\binom{2n+1}{2n+1-k}$$ for $0 \le k \le n$.
</s>