# Prove the identity $\binom{2n+1}{0} + \binom{2n+1}{1} + \cdots + \binom{2n+1}{n} = 4^n$

I've worked out a proof, but I was wondering about alternate, possibly more elegant ways to prove the statement. This is my (hopefully correct) proof:

Starting from the identity $2^m = \sum_{k=0}^m \binom{m}{k}$ (easily derived from the binomial theorem), with $m = 2n$:

$2^{2n} = 4^n = \binom{2n}{0} + \binom{2n}{1} + \cdots + \binom{2n}{2n-1} + \binom{2n}{2n}$

Applying the property $\binom{m}{k} = \binom{m}{m-k}$ to the second half of the list of summands in RHS above:

$4^n = \binom{2n}{0} + \binom{2n}{1} + \cdots + \binom{2n}{n-1} + \binom{2n}{n} + \underbrace{\binom{2n}{n-1} +\cdots \binom{2n}{1} + \binom{2n}{0}}_{\binom{m}{k} = \binom{m}{m-k} \text{ has been applied}}$

Rearranging the above sum by alternately taking terms from the front and end of the summand list in RHS above (and introducing the term $\binom{2n}{-1} = 0$ at the beginning just to make explicit the pattern being developed):

$4^n = (\binom{2n}{-1} + \binom{2n}{0}) + (\binom{2n}{0} + \binom{2n}{1}) + \cdots + (\binom{2n}{n-1} + \binom{2n}{n})$

Finally, using the property $\binom{m}{k} + \binom{m}{k-1} = \binom{m+1}{k}$ on the paired summands, we get the desired result:

$4^n = \binom{2n+1}{0} + \binom{2n+1}{1} + \cdots + \binom{2n+1}{n}$

Why not just \begin{align} 2^{2n+1} &=\binom{2n+1}{0}+\cdots+\binom{2n+1}{n}+\binom{2n+1}{n+1}+\cdots+\binom{2n+1}{2n+1} \\ &=\binom{2n+1}{0}+\cdots+\binom{2n+1}{n}+\binom{2n+1}{n}+\cdots+\binom{2n+1}{0} \\ &=2\left[\binom{2n+1}{0}+\cdots+\binom{2n+1}{n}\right] \end{align} Then divide each extremity by 2.
Applying what you mention on (in this context nicer) odd $2n+1$ instead of even $2n$ we find:$$2\times4^n=2^{2n+1}=\sum_{k=0}^{2n+1}\binom{2n+1}{k}=2\sum_{k=0}^{n}\binom{2n+1}{k}$$
Now divide by $2$.
• Side question: if by "$2.4$" you mean "$2\cdot4$", then what decimal representation do you use for $2+\frac{4}{10}$? – barak manos Jan 11 '16 at 11:24
• @barak In the Netherlands we write $2,4$. That's my (invalid) excuse for overlooking it. – drhab Jan 11 '16 at 12:22
Let $A$ be the powerset (i.e., the set of subsets of) of $\{1,\ldots,2n\}$. Let $B$ the set of all subsets of $\{1,\ldots,2n+1\}$ at most $n$ elements. Then "clearly" $|A|=2^{2n}=4^n$ and $|B|=\sum_{k=0}^n{2n+1\choose k}$. Define the following map $f\colon B\to A$: $$f(S)=\begin{cases}S&\text{if }2n+1\notin S\\\{1,\ldots,2n+1\}\setminus S&\text{if }2n+1\in S\end{cases}$$ and define $g\colon A\to B$ by $$g(S)=\begin{cases}S&\text{if }|S|\le n\\\{1,\ldots,2n+1\}\setminus S&\text{if }|S|>n\end{cases}$$ Finally, verify that $f$ and $g$ are inverse of each other, hence $|A|=|B|$.