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

• Hint: Add in the missing second half, from $n+1$ to $2n+1$. We do not need the identity you quoted. – André Nicolas Sep 20 '15 at 17:05

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

• I'm confused how you can just change the upper bound of the summation like that. – plast Sep 20 '15 at 17:37
• I added a relation used to get the equality of the sums. – mathcounterexamples.net Sep 20 '15 at 17:43

$$2^{2n}=\frac12\cdot 2^{2n+1}=\frac12\sum_{k=0}^{2n+1}{2n+1\choose k}=\frac12\sum_{k=0}^n\left({2n+1\choose k}+{2n+1\choose 2n+1-k}\right)$$

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

• ...well, something won't work, I am thinking on it. – peterh Sep 20 '15 at 17:11