$\frac{1}{2^n}\binom{n}{n}+\frac{1}{2^{n+1}}\binom{n+1}{n}+...+\frac{1}{2^{2n}}\binom{2n}{n}=1$: short proof?

Suppose you are flipping a coin until you get $n+1$ heads or $n+1$ tails. For $k=0,\dots,n$, what is the probability that you are done after exactly $n+1+k$ flips?

If the last flip was a tails, this means that in the former $n+k$ flips there were exactly $n$ tails, and this happens with probability $\frac{1}{2}\cdot\frac{1}{2^{n+k}}\binom{n+k}{n}$ (the first $\frac{1}{2}$ is due to assuming the last flip is tails). Same for heads, so the probability of finishing after exactly $n+1+k$ flips is $\frac{1}{2^{n+k}}\binom{n+k}{n}$.

Now just note that the number of flips always ends up between $n+1$ and $n+1+n$ (by pigeonhole principle).

Updated Solution

Here's a neater solution!

$$\begin{align} \sum_{k=0}^n \frac 1{2^{n+k}}\binom {n+k}n &=\frac 1{2^{2n}}\sum_{k=0}^n \binom {k+n}k 2^{n-k}\\ &=\frac 1{2^{2n}}\sum_{k=0}^n \binom {k+n}k \sum_{j=0}^{n-k}\binom {n-k}j\\ &=\frac 1{2^{2n}}\sum_{l=0}^n \binom {2n-l}{n-l}\sum_{j=0}^l \binom lj &&(l=n-k)\\ &=\frac 1{2^{2n}}\sum_{j=0}^n \sum_{l=j}^n\binom {2n-l}n\binom lj\\ &=\frac 1{2^{2n}}\sum_{j=0}^n \binom {2n+1}{n+j+1} &&(*)\\ &=\frac 1{2^{2n}}\sum_{j=n+1}^{2n+1} \binom {2n+1}j\\ &=\frac 1{2^{2n}}\cdot \frac 12\sum_{j=0}^{2n+1}\binom {2n+1}j &&\text{(by symmetry)}\\ &=\frac 1{2^{2n+1}}\cdot 2^{2n+1}\\ &=1\;\;\color{red}{\blacksquare}\end{align}$$

$\qquad \qquad \quad ^*\displaystyle\scriptsize\text{using }\sum_{r} \binom {a-r}{c}\binom {b+r}{d}=\binom {a+b+1}{c+d+1}$

---

Solution posted earlier

Here's a direct algebraic proof without using induction.

$$\begin{align} \sum_{k=0}^n \binom {k+n}k x^k(x+y)^{n-k} &=\sum_{k=0}^n \binom {k+n}k x^k\sum_{j=0}^{n-k}\binom {n-k}Jy^jx^{n-k-j}\\ &=\sum_{k=0}^n \binom{k+n}k\sum_{j=0}^{n-k}\binom{n-k}jy^jx^{n-j}\\ &=\sum_{\ell=0}^n\binom{2n-\ell}{n-\ell}\sum_{j=0}^\ell\binom{\ell}jy^jx^{n-j} &&(\ell=n-k)\\ &=\sum_{j=0}^n\sum_{\ell=j}^n (-1)^{n-\ell}\binom{-n-1}{n-\ell}(-1)^{\ell-j}\binom{-j-1}{\ell-j}y^jx^{n-j}\\ &=\sum_{j=0}^n(-1)^{n-j}y^jx^{n-j}\sum_{\ell=j}^n\binom{-n-1}{n-\ell}\binom{-j-1}{\ell-j}\\ &=\sum_{j=0}^n(-1)^{n-j}y^jx^{n-j}\binom{-n-j-2}{n-j} &&\text{(Vandermonde)}\\ &=\sum_{j=0}^n(-1)^{n-j}y^jx^{n-j}\cdot (-1)^{n-j}\binom{2n+1}{n-j}\\ &=\sum_{j=0}^n \binom{2n+1}{n-j}y^jx^{n-j}\\ &=\sum_{i=0}^n \binom{2n+1}i x^i y^{n-i}\\ \text{Put }x=y=1:\hspace{4cm}\\ \sum_{k=0}^n\binom {k+n}k2^{n-k} &=\sum_{i=0}^m\binom{2n+1}i &&(i=n-j)\\ &=\frac 12\cdot 2^{2n+1} &&\text{(by symmetry)}\\ &=2^{2n}\\ \sum_{k=0}^n \binom {n+k}k 2^{-k}&=2^n\\ \sum_{k=0}^n\frac 1{2^{n+k}} \binom {n+k}n&=1\\ \end{align}$$