<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] I would suggest to use induction:
For $n=1$:
$2^2 = \binom{3}{0}+\binom{3}{1}$, true.
For $m=n+1$:
$2^{2n+2}=4\cdot 2^{2n} = \sum_{k=0}^{n}\binom{2n+1}{k} + \binom{2n+2}{n+1} = 2^{2n} + \binom{2n+2}{n+1} = 2^{2n} + \frac{(2n+2)!}{(n+1)!^2}$
</s>