$\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? The identity $\frac{1}{2^n}\binom{n}{n}+\frac{1}{2^{n+1}}\binom{n+1}{n}+...+\frac{1}{2^{2n}}\binom{2n}{n}=1$ arises from a question on probability in my textbook. A proof by induction on $n$, which exploits the fact that $\binom{a}{b}+\binom{a}{b+1}=\binom{a+1}{b+1}$, is straightforward but not enlightening.
Is it possible to find any very clever approaches? Via a combinatorial or probabilistic interpretation, for instance?
 A: 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}$$
A: 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).
A: Here is an answer based upon generating functions. It is convenient to use the coefficient of operator $[z^n]$ to denote the coefficient of $z^n$ in a series. This way we can write e.g.
\begin{align*}
[z^k](1+z)^n=\binom{n}{k}
\end{align*}

We obtain
  \begin{align*}
\color{blue}{\sum_{k=0}^n\binom{n+k}{k}\frac{1}{2^{n+k}}}
&=\sum_{k=0}^n\binom{2n-k}{n-k}\frac{1}{2^{2n-k}}\tag{1}\\
&=\sum_{k=0}^\infty[z^{n-k}](1+z)^{2n-k}\frac{1}{2^{2n-k}}\tag{2}\\
&=2^{-2n}[z^n](1+z)^{2n}\sum_{k=0}^\infty\left(\frac{2z}{1+z}\right)^{k}\tag{3}\\
&=2^{-2n}[z^n](1+z)^{2n}\cdot\frac{1}{1-\frac{2z}{1+z}}\tag{4}\\
&=2^{-2n}[z^n](1+z)^{2n+1}\cdot\frac{1}{1-z}\tag{5}\\
&=2^{-2n}\sum_{k=0}^n[z^k](1+z)^{2n+1}\tag{6}\\
&=2^{-2n}\sum_{k=0}^n\binom{2n+1}{k}\tag{7}\\
&=2^{-2n}\frac{1}{2}2^{2n+1}\tag{8}\\
&\color{blue}{=1}
\end{align*}

Comment:


*

*In (1) we change the order of summation $k \rightarrow n-k$.

*In (2) we apply the coefficient of operator. We also set the limit to $\infty$ without changing anything since we are adding zeros only.

*In (3) we do a rearrangement and apply the formula $[z^{p-q}]A(z)=[z^p]z^qA(z)$.

*In (4) we apply the geometric series expansion.

*In (5) we do some simplifications.

*In (6) we do the Cauchy multiplication with the geometric series $\frac{1}{1-x}$ and restrict the upper limit of the sum with $n$ since other terms do not contribute to $[z^n]$.

*In (7) we select the coefficient of $z^k$.

*In (8) we apply the binomial theorem.
