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

Question

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?

Answer 1

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).

Answer 2

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

Answer 3

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.