# Prove $\sum_{k=0}^\infty \binom{2n+k+1}{n}/2^{2n+k+1}=1$.

I was trying to find a closed form for the sum $$\sum_{k=0}^\infty \binom{2n+k+1}{n}/2^{2n+k+1}$$.

According to Wolfram https://www.wolframalpha.com/input/?i=sum+(2n%2Bk%2B1)!%2F(n!*n%2Bk%2B1)!*2%5E(2n%2Bk%2B1))+from+k%3D0+to+infinity
this sum evaluates to 1, but I can't figure out how to prove this. Any hints.

• This maybe a far fetch but if you set a=2 in the formula under the subtitle "5. An asymptotic formula for the inversion numbers" in the following link, it may lead you to some clue: academic.csuohio.edu/bmargolius/homepage/inversions/invers.htm – NoChance May 5 '19 at 20:34
• @ZaeemHussain $\sum\limits_{k=0}^{\infty}\frac{\binom{2\,n+k+1}{n}}{2^{2\,n+k+1}}=\frac{\sqrt{\pi }\,\Gamma(n+2)}{2^{2\,n+1}\Gamma \left(\frac{1}{2} (2\,n+3)\right)}\binom{2\,n+1}{n} =1$ perhaps provides some insight. – Steven Clark May 5 '19 at 21:32

Preliminary \begin{align} a_n &=\sum_{k=0}^n\frac{\binom{k+n}{k}}{2^k}\tag{1a}\\ &=\sum_{k=0}^n\frac{\binom{k+n-1}{k-1}+\binom{k+n-1}{k}}{2^k}\tag{1b}\\ &=\sum_{k=0}^{n-1}\frac{\binom{k+n}{k}}{2^{k+1}}+\sum_{k=0}^n\frac{\binom{k+n-1}{k}}{2^k}\tag{1c}\\ &=\frac12a_n-\frac{\binom{2n}{n}}{2^{n+1}}+a_{n-1}+\frac{\binom{2n-1}{n}}{2^n}\tag{1d}\\[3pt] &=\frac12a_n+a_{n-1}\tag{1e}\\[9pt] &=2a_{n-1}\tag{1f} \end{align} Explanation:
$$\text{(1a)}$$: define $$a_n$$
$$\text{(1b)}$$: Pascal Identity
$$\text{(1c)}$$: substitute $$k\mapsto k+1$$ in the left sum
$$\text{(1d)}$$: apply $$\text{(1a)}$$
$$\text{(1e)}$$: cancel terms
$$\text{(1f)}$$: $$2$$ times $$\text{(1e)}$$ minus $$\text{(1a)}$$

Since $$a_0=1$$, we get $$\sum_{k=0}^n\frac{\binom{k+n}{k}}{2^k}=2^n\tag2$$

Answer \begin{align} \sum_{k=0}^\infty\frac{\binom{2n+k+1}{n}}{2^{2n+k+1}} &=\sum_{k=0}^\infty\frac{\binom{2n+k+1}{n+k+1}}{2^{2n+k+1}}\tag{3a}\\ &=\frac1{2^n}\sum_{k=0}^\infty(-1)^{n+k+1}\frac{\binom{-n-1}{n+k+1}}{2^{n+k+1}}\tag{3b}\\ &=\frac1{2^n}\sum_{k=n+1}^\infty(-1)^k\frac{\binom{-n-1}{k}}{2^k}\tag{3c}\\ &=\frac1{2^n}2^{n+1}-\frac1{2^n}\sum_{k=0}^n(-1)^k\frac{\binom{-n-1}{k}}{2^k}\tag{3d}\\ &=2-\frac1{2^n}\sum_{k=0}^n\frac{\binom{k+n}{k}}{2^k}\tag{3e}\\[9pt] &=1\tag{3f} \end{align} Explanation:
$$\text{(3a)}$$: symmetry of Pascal's Triangle
$$\text{(3b)}$$: negative binomial coefficient
$$\text{(3c)}$$: substitute $$k\mapsto k-n-1$$
$$\text{(3d)}$$: Binomial Theorem
$$\text{(3e)}$$: negative binomial coefficient
$$\text{(3f)}$$: apply $$(2)$$

Recall that $$\binom nm=\frac1{2\pi i}\oint_{|z|=\rho}\frac{(1+z)^n}{z^{m+1}}dz.\tag1$$ Therefore, assuming $$\rho<1$$: \begin{align} \sum_{k=0}^\infty \binom{2n+k+1}{n}\left(\frac12\right)^{2n+k+1} &=\sum_{k=0}^\infty\left(\frac12\right)^{2n+k+1}\frac1{2\pi i}\oint_{|z|=\rho}\frac{(1+z)^{2n+k+1}}{z^{n+1}}dz\tag2\\ &=\frac1{2\pi i}\oint_{|z|=\rho}\left(\frac{1+z}2\right)^{2n+1}\frac{dz}{z^{n+1}} \sum_{k=0}^\infty\left(\frac{1+z}2\right)^{k}\tag3\\ &=\frac1{2\pi i}\oint_{|z|=\rho}\left(\frac{1+z}2\right)^{2n+1} \frac1{1-\frac{1+z}2}\frac{dz}{z^{n+1}}\tag4\\ &=\frac1{2\pi i}\oint_{|z|=\rho}\left(\frac{1+z}2\right)^{2n+1} \frac2{1-z}\frac{dz}{z^{n+1}}\tag5\\ &=\operatorname{Res}_{z=0}\left(\frac12\right)^{2n}\frac{1}{z^{n+1}} \sum_{l=0}^{2n+1}\binom{2n+1}l z^l\sum_{k=0}^\infty z^k\tag6\\ &=\left(\frac12\right)^{2n}\sum_{k=0}^n\binom{2n+1}{n-k}\tag7\\ &=\left(\frac12\right)^{2n}2^{2n}=1.\tag8 \end{align}

Explanations:

$$(1)$$ Follows from the residue theorem, since $$\binom nm$$ is the coefficient at $$z^{-1}$$ in the Laurent expansion of the integrand about $$z=0$$.

$$(2)$$ The binomial coefficient is replaced according to $$(1)$$.

$$(3)$$ The terms are rearranged and the order of integration and summation is interchanged (which is possible due to $$\rho <1$$).

$$(4)$$ The geometric series is evaluated (which converges due to $$\rho <1$$).

$$(5)$$ The result for the geometric series is rearranged.

$$(6)$$ The residue theorem is applied. The terms $$(1+z)^{2n+1}$$ and $$\dfrac1 {1-z}$$ are expanded to binomial sum and geometric series, respectively.

$$(7)$$ The residue, i.e. the coefficient at $$z^{-1}$$, is evaluated.

$$(8)$$ The sum of the binomial coefficients is evaluated to $$2^{2n}$$ (since $$2n+1$$ is odd and exactly half of binomial coefficients is summed) which gives rise to the final result.

• Thanks. Could you also point me to a reference for the formula relating the binomial coefficient to contour integration that you have in the beginning of the answer? Since I am not familiar with it I also couldn't follow the step where you get rid of the integral. – Zaeem Hussain May 5 '19 at 23:28
• @ZaeemHussain I have added some explanations. Please let me know if it helps. – user May 6 '19 at 6:06