# Prove the following relation:

I must prove the relation $$\sum_{k=0}^{n+1}\binom{n+k+1}{k}\frac1{2^k}=2\sum_{k=0}^n\binom{n+k}{k}\frac1{2^k}.$$

I got this far before I got stuck:

$\begin{eqnarray*} \sum_{k=0}^{n+1}\binom{n+k+1}{k}\frac1{2^k} & = & \sum_{k=0}^{n+1}\left\{\binom{n+k}{k}+\binom{n+k}{k-1}\right\}\frac1{2^k}\\ & = & \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+1}{n}\frac1{2^k}. \end{eqnarray*}$

If I can combine the second and third terms and get something same as first term, I am done but I could not do that.

• It seems you are having indexing problems, too. When k is zero, you start with n choose -1 in your last expression. – davidlowryduda Nov 3 '12 at 18:59
• Would that a problem? I mean in the second term, k=0 and k=1 would mean same thing since n choose -1 would mean 0 right? Or am I wrong? – 007resu Nov 3 '12 at 19:02
• @mixedmath: Not a problem: $\binom{n}{-1}=0$. – Brian M. Scott Nov 3 '12 at 19:04
• @mixedmath: It is a (not un)common convention to take $\binom{n}{n+1}=\binom{n}{-1}=0$. – Cameron Buie Nov 3 '12 at 19:05
• thanks @CameronBuie for the edit! – 007resu Nov 3 '12 at 19:44

Let $s_n=\displaystyle\sum_{k=0}^n\binom{n+k}k\frac1{2^k}$. Then

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

and therefore

\begin{align*} s_{n+1}&=2s_n+\binom{2n+1}{n+1}\frac1{2^n}-\binom{2n+2}{n+1}\frac1{2^{n+1}}\\ &=2s_n+\frac1{2^{n+1}}\left(2\binom{2n+1}{n+1}-\binom{2n+2}{n+1}\right)\\ &=2s_n+\frac1{2^{n+1}}\left(2\binom{2n+1}{n+1}-\binom{2n+1}{n+1}-\binom{2n+1}n\right)\\ &=2s_n+\frac1{2^{n+1}}\left(\binom{2n+1}{n+1}-\binom{2n+1}n\right)\\ &=2s_n\;. \end{align*}

• Simply Elegant! – 007resu Nov 3 '12 at 20:55
• @user1710036: Thank you! – Brian M. Scott Nov 3 '12 at 20:58

You correctly used Pascal's identity, but then you goofed going to the next line. (Should have an $n$ in that last exponent of $2$, not a $k$.) I recommend going a different way, though.

$\begin{eqnarray*} \sum_{k=0}^{n+1}\binom{n+k+1}{k}\frac1{2^k} & = & \sum_{k=0}^{n+1}\left\{\binom{n+k}{k}+\binom{n+k}{k-1}\right\}\frac1{2^k}\\ & = & \sum_{k=0}^{n+1}\binom{n+k}{k}\frac1{2^k}+\sum_{k=0}^{n+1}\binom{n+k}{k-1}\frac1{2^k}\\ & = & \sum_{k=0}^{n+1}\binom{n+k}{k}\frac1{2^k}+\sum_{k=1}^{n+1}\binom{n+k}{k-1}\frac1{2^k}\\ & = & \sum_{k=0}^{n+1}\binom{n+k}{k}\frac1{2^k}+\sum_{k=0}^n\binom{n+k+1}{k}\frac1{2^{k+1}}\\ & = & -\binom{2n+2}{n+1}\frac1{2^{n+2}}+\sum_{k=0}^{n+1}\binom{n+k}{k}\frac1{2^k}+\sum_{k=0}^{n+1}\binom{n+k+1}{k}\frac1{2^{k+1}}\\ & = & -\binom{2n+2}{n+1}\frac1{2^{n+2}}+\sum_{k=0}^{n+1}\binom{n+k}{k}\frac1{2^k}+\frac12\sum_{k=0}^{n+1}\binom{n+k+1}{k}\frac1{2^k}. \end{eqnarray*}$

You see how we have half the original sum on the right-hand side now? If we subtract that and then multiply by $2$, we have

$\begin{eqnarray*} \sum_{k=0}^{n+1}\binom{n+k+1}{k}\frac1{2^k} & = & -\binom{2n+2}{n+1}\frac1{2^{n+1}}+2\sum_{k=0}^{n+1}\binom{n+k}{k}\frac1{2^k}\\ & = & -\binom{2n+2}{n+1}\frac1{2^{n+1}}+2\binom{2n+1}{n+1}\frac1{2^{n+1}}+2\sum_{k=0}^n\binom{n+k}{k}\frac1{2^k}. \end{eqnarray*}$

Finally, applying Pascal's identity to $\binom{2n+2}{n+1}$, and using the fact that $\binom{2n+1}{n}=\binom{2n+1}{n+1},$ the extraneous binomial coefficients cancel out, and we're left with $$\sum_{k=0}^{n+1}\binom{n+k+1}{k}\frac1{2^k}=2\sum_{k=0}^n\binom{n+k}{k}\frac1{2^k},$$ as desired.

• Thanks! the k was actually a typing mistake there. I intended to write n. – 007resu Nov 3 '12 at 20:41

By way of enrichment here is another algebraic proof using basic complex variables.

Suppose we are trying to show that $$\sum_{k=0}^{n+1} {n+1+k\choose k} \frac{1}{2^k} = 2 \sum_{k=0}^n {n+k\choose k} \frac{1}{2^k}.$$

Introduce the integral representations $${n+1+k\choose k} = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{n+1+k}}{z^{k+1}} \; dz.$$

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

Now the first term in the numerator clearly gives a zero contribution so we get $$2\times \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{n+1}}{1-z} \frac{(1+z)^{n+2}}{z^{n+2} 2^{n+2}} \; dz \\ \frac{1}{2^{n+1}} \times \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{2n+3}}{1-z} \frac{1}{z^{n+2}} \; dz.$$ Extracting the residue we find $$\frac{1}{2^{n+1}} \sum_{q=0}^{n+1} {2n+3\choose q} = \frac{1}{2^{n+2}} \sum_{q=0}^{2n+3} {2n+3\choose q} = \frac{1}{2^{n+2}} 2^{2n+3} = 2^{n+1}.$$

Now the RHS is just twice the LHS with $n+1$ replaced by $n$ so we get $$2\times 2^n = 2^{n+1}$$ and the two are indeed the same as claimed.

We have not made use of the properties of complex integrals here so this computation can also be presented using just algebra of generating functions.

Apparently this method is due to Egorychev although some of it is probably folklore.