4
$\begingroup$

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.

  • 0
    thanks @CameronBuie for the edit!2012-11-03

3 Answers 3

6

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

  • 0
    @user1710036: Thank you!2012-11-03
2

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.

  • 0
    Thanks! the k was actually a typing mistake there. I intended to write n.2012-11-03
0

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.