# Proving this binomial identity $\sum_{k=0}^n {n+k \choose k} \frac{1}{2^{k}}= 2^{n}$

A teacher gave this as a homework question, and I have tried but haven't been able to arrive at a solution.
$\sum_{k=0}^n {n+k \choose k} \frac{1}{2^{k}}= 2^{n}$
Could someone prove it, or at least point me in the right direction ?

A proof by induction is possible, if a bit messy. For $n\in\Bbb N$ let $$s_n=\sum_{k=0}^n\binom{n+k}k\frac1{2^k}\;.$$ Clearly $s_0=1=2^0$. Suppose that $s_n=2^n$ for some $n\in\Bbb N$. Then

\begin{align*} s_{n+1}&=\sum_{k=0}^{n+1}\binom{n+1+k}k\frac1{2^k}\\\\ &=\binom{2n+2}{n+1}\frac1{2^{n+1}}+\sum_{k=0}^n\left(\binom{n+k}k+\binom{n+k}{k-1}\right)\frac1{2^k}\\\\ &=\binom{2n+2}{n+1}\frac1{2^{n+1}}+\sum_{k=0}^n\binom{n+k}k\frac1{2^k}+\sum_{k=0}^n\binom{n+k}{k-1}\frac1{2^k}\\\\ &=\binom{2n+2}{n+1}\frac1{2^{n+1}}+\sum_{k=0}^n\binom{n+k}k\frac1{2^k}+\sum_{k=1}^n\binom{n+k}{k-1}\frac1{2^k}\\\\ &=\binom{2n+2}{n+1}\frac1{2^{n+1}}+s_n+\sum_{k=0}^{n-1}\binom{n+1+k}k\frac1{2^{k+1}}\\\\ &=s_n+\binom{2n+2}{n+1}\frac1{2^{n+1}}+\frac12\sum_{k=0}^{n-1}\binom{n+1+k}k\frac1{2^k}\\\\ &=2^n+\left(\binom{2n+1}{n+1}+\binom{2n+1}n\right)\frac1{2^{n+1}}+\frac12\sum_{k=0}^{n-1}\binom{n+1+k}k\frac1{2^k}\\\\ &=2^n+\binom{2n+1}{n+1}\frac1{2^{n+1}}+\frac12\sum_{k=0}^n\binom{n+1+k}k\frac1{2^k}\\\\ &\overset{(*)}=2^n+\frac12\binom{2n+2}{n+1}\frac1{2^{n+1}}+\frac12\sum_{k=0}^n\binom{n+1+k}k\frac1{2^k}\\\\ &=2^n+\frac12\sum_{k=0}^{n+1}\binom{n+1+k}k\frac1{2^k}\\\\ &=2^n+\frac12s_{n+1}\;, \end{align*}

where the step $(*)$ follows from the fact that

$$\binom{2n+2}{n+1}=\binom{2n+1}{n+1}+\binom{2n+1}n=2\binom{2n+1}{n+1}\;.$$

Thus, $\frac12s_{n+1}=2^n$, and $s_{n+1}=2^{n+1}$, as desired.

Added: I just came up with a combinatorial argument as well. Flip a fair coin until either $n+1$ heads or $n+1$ tails have appeared. Let $k$ be the number of times the other face of the coin has appeared; clearly $0\le k\le n$. The last flip must result in the $(n+1)$-st instance of the majority face, but the other $n$ instances of that face and $k$ of the other can appear in any order.

Now imagine that after achieving the desired outcome we continue to flip the coin until we’ve flipped it $2n+1$ times. There are altogether

$$\binom{n+k}k2^{(2n+1)-(n+k)}=\binom{n+k}k2^{n+1-k}$$

sequences of $2n+1$ flips that decide the outcome at the $(n+k+1)$-st toss, so

$$\sum_{k=0}^n\binom{n+k}k2^{n+1-k}=2^{2n+1}\;,$$

and

$$\sum_{k=0}^n\binom{n+k}k\frac1{2^k}=2^n\;.$$

• Now that I read your answer a bit closer, I note that my answer seems to be along the same lines. If you think they are too close, I will delete mine. – robjohn Jan 31 '15 at 23:03
• @robjohn: It’s essentially the same as my induction argument, but the annotations might help someone. – Brian M. Scott Jan 31 '15 at 23:08

Since $$\binom{2n-1}{n}+\binom{2n-1}{n-1}=\binom{2n}{n}\quad\text{and}\quad\binom{2n-1}{n}=\binom{2n-1}{n-1}\tag{1}$$ we have $$\binom{2n-1}{n}=\frac12\binom{2n}{n}\tag{2}$$ Therefore, if we define \begin{align} A_n &=\sum_{k=0}^n\binom{n+k}{k}\frac1{2^k}\tag{3a}\\ &=\sum_{k=0}^n\left[\binom{n+k-1}{k}+\binom{n+k-1}{k-1}\right]\frac1{2^k}\tag{3b}\\ &=\sum_{k=0}^n\binom{n+k-1}{k}\frac1{2^k}\\ &+\sum_{k=0}^{n-1}\binom{n+k}{k}\frac1{2^{k+1}}\tag{3c}\\ &=\sum_{k=0}^{n-1}\binom{n+k-1}{k}\frac1{2^k}+\binom{2n-1}{n}\frac1{2^n}\\ &+\sum_{k=0}^n\binom{n+k}{k}\frac1{2^{k+1}}-\binom{2n}{n}\frac1{2^{n+1}}\tag{3d}\\ &=\sum_{k=0}^{n-1}\binom{n+k-1}{k}\frac1{2^k}+\sum_{k=0}^n\binom{n+k}{k}\frac1{2^{k+1}}\tag{3e}\\ &=A_{n-1}+\frac12A_n\tag{3f} \end{align} Explanation:
$\text{(3a)}$: define $A_n$
$\text{(3b)}$: use Pascal's Triangle
$\text{(3c)}$: substitute $k\mapsto k+1$ in the second sum
$\text{(3d)}$: add and subtract the last term in each sum
$\text{(3e)}$: use $(2)$ to cancel the terms separated in $\text{(3d)}$
$\text{(3f)}$: use the definition of $A_n$

Thus, $\text{(3f)}$ implies that $$A_n=2A_{n-1}\tag{4}$$ Since $A_0=1$, we get that $$A_n=2^n\tag{5}$$

• +1. Clever answer. At the beginning I didn't notice it was a finite sum. – Felix Marin Feb 1 '15 at 21:33
• @FelixMarin: yeah, the finiteness is a hitch. However, I have not yet succeeded in getting this identity without induction. – robjohn Feb 1 '15 at 21:43

This one can also be done using complex variables.

Suppose we seek to show that $$\sum_{k=0}^{n} {n+k \choose k} \frac{1}{2^k} = 2^n.$$ Introduce the integral repesentation $${n+k\choose k} = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{n+k}}{z^{k+1}} \; dz.$$

This gives for the sum $$\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{n}}{z} \sum_{k=0}^n \frac{(1+z)^k}{(2z)^k} \; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{n}}{z} \frac{(1+z)^{n+1}/(2z)^{n+1}-1}{(1+z)/(2z)-1} \; dz \\ = \frac{2}{2\pi i} \int_{|z|=\epsilon} (1+z)^n \frac{(1+z)^{n+1}/(2z)^{n+1}-1}{(1+z)-2z} \; dz \\ = \frac{2}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^n}{1-z} \left((1+z)^{n+1}/(2z)^{n+1}-1\right) \; dz.$$

The second component makes no contribution inside the contour, leaving just $$\frac{2^{-n}}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n+1}} \frac{(1+z)^{2n+1}}{1-z} \; dz.$$ Extracting coefficients we get $$2^{-n} [z^n] \frac{(1+z)^{2n+1}}{1-z} = 2^{-n} \sum_{q=0}^n {2n+1\choose q} = 2^{-n}\times \frac{1}{2} \times 2^{2n+1} = 2^n.$$

Binomial coefficient is just $\binom{-(n-1)}{k} = (-1)^k \binom{n+k}{k}$ and take $x= -\frac{1}{2}$so you get $\sum_{k=0}^{\infty} \binom{-(n-1)}{k} x^k = \frac{1}{(1-x)^{n-1}}$

• How does that solve the problem? The sum in question is finite. – darij grinberg Jan 31 '15 at 21:13
• Two corrections: $\binom{\color{red}{-n-1}}{k}=(-1)^k\binom{n+k}{k}$, and $\sum_{k=0}^\infty\binom{\color{red}{-n-1}}k x^k=\frac1{(1\color{red}{+}x)^{\color{red}{-n-1}}}$. Your method proves that $\sum_{k=0}^\infty \binom{n+k}{k}2^{-k}=2^{n+1}$, which is interesting, but not what was asked. – Mike Earnest Apr 26 '18 at 18:14

Here is a probabilistic proof of your equality, which I will write as $$\sum_{k=0}^n\binom{n+k}{k}2^{-(n+k)}=1$$ Consider a rectangular lattice of $(n+2)^2$ points, where the lower left point is $(0,0)$ and the upper right is $(n+1,n+1)$. An ant starts at $(0,0)$, and once per second, randomly chooses to take a step upwards or to the right. Furthermore, imagine the topmost row $\{(x,n+1):0\le x\le n\}$ and rightmost column $\{(n+1,y):0\le y\le n\}$ are covered in glue, so the ant stops moving once it reaches one of these points.

Eventually, the ant will get stuck. You can show that the probability the ant gets stuck at $(k,n+1)$ is equal to $\binom{n+k}{k}2^{-(n+k)}\cdot\frac12$ by considering all the possible paths that bring it to that point. Therefore, the probability the ant gets stuck at either $(k,n+1)$ or $(n+1,k)$ is equal to $$\binom{n+k}{k}2^{-(n+k)}$$ Since the ant gets stuck at exactly one of these point, the sum of these probabilities must equal $1$.