3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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 $\endgroup$ – NoChance May 5 '19 at 20:34
  • $\begingroup$ @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. $\endgroup$ – Steven Clark May 5 '19 at 21:32
1
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
4
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Zaeem Hussain May 5 '19 at 23:28
  • $\begingroup$ @ZaeemHussain I have added some explanations. Please let me know if it helps. $\endgroup$ – user May 6 '19 at 6:06

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.