<s>[INST] $\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?
 [/INST] 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).
</s>