10
$\begingroup$

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?

$\endgroup$
13
$\begingroup$

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

$\endgroup$
5
$\begingroup$

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

$\endgroup$
  • $\begingroup$ @robjohn - Thank you - very kind of you! $\endgroup$ – hypergeometric Sep 1 '17 at 7:13
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.