A summation similar to Vandermonde identity

Question

I met an identity, similar to Vandermonde's identity, but not sure how to prove:

$$\sum_{j=0}^k{k \choose j}{\frac{1}{2}j \choose n}(-1)^{n+k-j}=\frac{k}{n}(-1)^k2^{k-2n}{2n-k-1 \choose n-1}, \ n \geq k \geq0.$$

You may find this identity in Section 6 of "2018The computation of the probability density and distribution functions for some families of random variables by means of the Wynn-p accelerated Post-Widder formula" and Appendix of "2007Bayesian nonparametric estimation of the probability of discovering new species".

I cannot see how to apply Vandermonde's identity here, although they are similar.

Any help is appreciated.

Answer 1

We seek to show that

$$\sum_{j=0}^k {k\choose j} {j/2\choose n} (-1)^{n-j} = \frac{k}{n} 2^{k-2n} {2n-k-1\choose n-1}$$

where $n\ge k\ge 0.$ Here we have removed the factor $(-1)^k$ which is present on both sides. We get for the even component

$$\sum_{p=0}^{\lfloor k/2 \rfloor} {k\choose 2p} {p\choose n} (-1)^{n} = 0$$

because $n\gt p$ and $p\ge 0.$ This leaves the odd component

$$- (-1)^{n} \sum_{p=0}^{\lfloor (k-1)/2 \rfloor} {k\choose 2p+1} {p+1/2\choose n}.$$

Now we have

$${p+1/2\choose n} = \frac{1}{n!} \prod_{q=0}^{n-1} (p+1/2-q) = \frac{1}{2^n n!} \prod_{q=0}^{n-1} (2p+1-2q) \\ = \frac{1}{2^n n!} \prod_{q=0}^{p} (2p+1-2q) \prod_{q=p+1}^{n-1} (2p+1-2q) \\ = \frac{1}{2^n n!} \frac{(2p+2)!}{2^{p+1} (p+1)!} (-1)^{n-p-1} \prod_{q=p+1}^{n-1} (2q-2p-1) \\ = \frac{1}{2^n n!} \frac{(2p+2)!}{2^{p+1} (p+1)!} (-1)^{n-p-1} \frac{(2n-2p-2)!}{2^{n-p-1} (n-p-1)!} \\ = \frac{(-1)^{n-p-1} (2n)!}{2^{2n} n!^2} {2n\choose 2p+2}^{-1} {n\choose p+1} \\ = \frac{(-1)^{n-p-1}}{2^{2n}} {2n\choose n} {2n\choose 2p+2}^{-1} {n\choose p+1}.$$

where $p\lt n.$ It will be helpful to re-write this as

$$\frac{p+1}{n} \frac{(-1)^{n-p-1}}{2^{2n}} {2n\choose n} {2n-1\choose 2p+1}^{-1} {n\choose p+1} \\ = \frac{(-1)^{n-p-1}}{2^{2n}} {2n\choose n} {2n-1\choose 2p+1}^{-1} {n-1\choose p}.$$

We thus get for our sum

$$\frac{1}{2^{2n}} {2n\choose n} \sum_{p=0}^{\lfloor (k-1)/2 \rfloor} (-1)^p {k\choose 2p+1} {2n-1\choose 2p+1}^{-1} {n-1\choose p}.$$

Now observe that

$${k\choose 2p+1} {2n-1\choose 2p+1}^{-1} = \frac{k!}{(k-2p-1)!} \frac{(2n-2p-2)!}{(2n-1)!} \\ = {2n-1\choose k}^{-1} {2n-2p-2\choose k-2p-1}.$$

This yields for the sum

$$\frac{1}{2^{2n}} {2n\choose n} {2n-1\choose k}^{-1} \sum_{p=0}^{\lfloor (k-1)/2 \rfloor} (-1)^p {2n-2p-2\choose k-2p-1} {n-1\choose p}.$$

Now to treat the remaining sum we have

$$[z^{k}] (1+z)^{2n-2} \sum_{p=0}^{\lfloor (k-1)/2 \rfloor} (-1)^p z^{2p+1} (1+z)^{-2p} {n-1\choose p}.$$

The coefficient extractor enforces the upper limit $\lfloor (k-1)/2\rfloor \ge p$ so we may continue with

$$[z^{k}] (1+z)^{2n-2} \sum_{p\ge 0} (-1)^p z^{2p+1} (1+z)^{-2p} {n-1\choose p} \\ = [z^{k}] (1+z)^{2n-2} z \left(1-\frac{z^2}{(1+z)^2}\right)^{n-1} \\ = [z^{k}] z (1+2z)^{n-1}.$$

This means for $k=0$ the sum is zero. For $k\ge 1$ we get including the factor in front

$$\bbox[5px,border:2px solid #00A000]{ \frac{1}{2^{2n}} {2n\choose n} {2n-1\choose k}^{-1} {n-1\choose k-1} 2^{k-1}.}$$

To simplify this we expand the binomial coefficients

$$\frac{1}{2^{2n-k+1}} \frac{(2n)!\times k! \times (2n-1-k)! \times (n-1)!} {n! \times n! \times (2n-1)! \times (k-1)! \times (n-k)!} \\ = \frac{1}{2^{2n-k+1}} \frac{(2n)\times k \times (2n-1-k)!} {n \times n! \times (n-k)!} \\ = \frac{1}{2^{2n-k}} \frac{k \times (2n-1-k)!} {n! \times (n-k)!}.$$

This yields at last

$$\bbox[5px,border:2px solid #00A000]{ \frac{1}{2^{2n-k}} \frac{k}{n} {2n-1-k\choose n-1}.}$$

Answer 2

$\newcommand{\bbx}[1]{\,\bbox[15px,border:1px groove navy]{\displaystyle{#1}}\,} \newcommand{\braces}[1]{\left\lbrace\,{#1}\,\right\rbrace} \newcommand{\bracks}[1]{\left\lbrack\,{#1}\,\right\rbrack} \newcommand{\dd}{\mathrm{d}} \newcommand{\ds}[1]{\displaystyle{#1}} \newcommand{\expo}[1]{\,\mathrm{e}^{#1}\,} \newcommand{\ic}{\mathrm{i}} \newcommand{\mc}[1]{\mathcal{#1}} \newcommand{\mrm}[1]{\mathrm{#1}} \newcommand{\pars}[1]{\left(\,{#1}\,\right)} \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}} \newcommand{\root}[2][]{\,\sqrt[#1]{\,{#2}\,}\,} \newcommand{\totald}[3][]{\frac{\mathrm{d}^{#1} #2}{\mathrm{d} #3^{#1}}} \newcommand{\verts}[1]{\left\vert\,{#1}\,\right\vert}$ \begin{align} &\bbox[4px,#ffd]{\sum_{j = 0}^{k}{k \choose j}{j/2 \choose n} \pars{-1}^{n + k - j}} = \pars{-1}^{n + k}\sum_{j = 0}^{k}{k \choose j}\pars{-1}^{j} \bracks{z^{n}}\pars{1 + z}^{\, j/2} \\[5mm] &\ = \pars{-1}^{n + k}\bracks{z^{n}}\sum_{j = 0}^{k}{k \choose j} \pars{-\root{1 + z}}^{j} = \pars{-1}^{n + k}\bracks{z^{n}}\pars{1 - \root{1 + z}}^{k} \end{align} The last expresion vanishes out whenever $\ds{n < k}$ because $\ds{\pars{1 - \root{1 + z}}^{k} \sim \pars{-1/2}^{k}\,\color{red}{z^{k}}}$ as $\ds{\verts{z}\ \to\ 0}$. Then, $$ \bbox[4px,#ffd]{\sum_{j = 0}^{k}{k \choose j}{j/2 \choose n} \pars{-1}^{n + k - j}} = \pars{-1}^{n + k}\bracks{n \geq k} \oint_{\mathcal{C}} {\pars{1 - \root{1 + z}}^{k} \over z^{n + 1}} \,{\dd z \over 2\pi\ic} $$ $\ds{\mathcal{C}}$ is a key-hole contour which take full advantage of the $\ds{\root{1 + z}}$ principal branch-cut along $\ds{\left(-\infty,-1\right]}$: \begin{align} &\bbox[4px,#ffd]{\sum_{j = 0}^{k}{k \choose j}{j/2 \choose n} \pars{-1}^{n + k - j}} \\[5mm] = & \pars{-1}^{n + k}\bracks{n \geq k}\left[% \int_{-\infty}^{-1}{\pars{1 - \ic\root{-1 - x}}^{k} \over x^{n + 1}}\,{\dd x \over 2\pi\ic}\right. \\[2mm] &\ \phantom{\pars{-1}^{n + k}\bracks{n \geq k}} + \left.\int_{-1}^{-\infty}{\pars{1 + \ic\root{-1 - x}}^{k} \over x^{n + 1}}\,{\dd x \over 2\pi\ic}\right] \\[5mm] = &\ \pars{-1}^{n + k}\bracks{n \geq k}\left[% \int_{1}^{\infty}{\pars{1 - \ic\root{x - 1}}^{k} \over \pars{-1}^{n + 1}\, x^{n + 1}}\,{\dd x \over 2\pi\ic}\right. \\[2mm] &\ \phantom{\pars{-1}^{n + k}\bracks{n \geq k}} -\left.\int_{1}^{\infty} {\pars{1 + \ic\root{x - 1}}^{-k} \over \pars{-1}^{n + 1}\, x^{n + 1}}\,{\dd x \over 2\pi\ic}\right] \\[5mm] = &\ {\pars{-1}^{k} \over \pi}\,\bracks{n \geq k} \,\Im\int_{1}^{\infty} {\pars{1 + \ic\root{x - 1}}^{k} \over x^{n + 1}}\,\dd x \label{1}\tag{1} \end{align} With $\ds{x = \sec^{2}\pars{\theta}}$: \begin{align} &\bbox[4px,#ffd]{\sum_{j = 0}^{k}{k \choose j}{j/2 \choose n} \pars{-1}^{n + k - j}} \\[5mm] = &\ {2\pars{-1}^{k} \over \pi}\,\bracks{n \geq k} \int_{0}^{\pi/2} \cos^{2n - k - 1}\pars{\theta} \sin\pars{\theta}\sin\pars{k\theta}\,\dd\theta \\[5mm] = &\ {\pars{-1}^{k} \over \pi}\,\bracks{n \geq k} \pars{I_{2n - k - 1,1 - k} - I_{2n - k -1,1 + k}} \label{2}\tag{2} \\[5mm] &\ \mbox{where}\quad I_{\ell,m} \equiv \Re\int_{0}^{\pi/2}\cos^{\ell}\pars{\theta} \expo{\ic m\theta}\dd\theta \end{align}

---

$\ds{\large I_{\ell m}\ Evaluation:}$ \begin{align} I_{\ell,m} & \equiv \Re\int_{0}^{\pi/2}\cos^{\ell}\pars{\theta} \expo{\ic m\theta}\dd\theta \\[5mm] & = \left.\Re\int_{\theta\ =\ 0}^{\theta\ =\ \pi/2} \pars{z + 1/z \over 2}^{\ell}z^{m}\, {\dd z \over \ic z}\right\vert_{\ z\ =\ \exp\pars{\ic\theta}} \\[5mm] & = \left.{1 \over 2^{\ell}}\,\Im\int_{\theta\ =\ 0}^{\theta\ =\ \pi/2} \pars{1 + z^{2}}^{\ell}\, z^{m -\ell - 1}\, \dd z\,\,\right\vert_{\ z\ =\ \exp\pars{\ic\theta}} \\[5mm] & \stackrel{\mrm{as}\ \epsilon\ \to\ 0^{+}}{\sim}\,\,\, -\,{1 \over 2^{\ell}}\,\Im\int_{1}^{\epsilon} \pars{1 - y^{2}}^{\ell}\, \expo{\ic\pars{m - \ell - 1}\pi/2} y^{m -\ell - 1}\,\ic\,\dd y \\[2mm] & \phantom{ \stackrel{\mrm{as}\ \epsilon\ \to\ 0^{+}}{\sim}\,\,\,} -\,{1 \over 2^{\ell}} \Im\int_{\pi/2}^{0}\epsilon^{m - \ell - 1} \expo{\ic\pars{m - \ell - 1}\theta} \epsilon\expo{\ic\theta}\ic\,\dd \theta \\[5mm] & = {\sin\pars{\bracks{m - \ell}\pi/2} \over 2^{\ell}\pars{m - \ell}} \int_{y\ =\ \epsilon}^{y\ =\ 1} \pars{1 - y^{2}}^{\ell}\,\dd\pars{y^{m -\ell}} \\[2mm] & + {\epsilon^{m - \ell} \over 2^{\ell}}\, {\sin\pars{\bracks{m - l}\pi/2} \over m - \ell} \\[5mm] & = {\sin\pars{\bracks{m - \ell}\pi/2} \over 2^{\ell}\pars{m - \ell}} \braces{-\epsilon^{m - \ell} -\int_{\epsilon}^{1} y^{m -\ell}\bracks{\ell\pars{1 - y^{2}}^{\ell - 1}\pars{-2y}} \,\dd y} \\[2mm] & + {\epsilon^{m - \ell} \over 2^{\ell}}\, {\sin\pars{\bracks{m - \ell}\pi/2} \over m - \ell} \\[5mm] & \stackrel{\mrm{as}\ \epsilon\ \to\ 0^{+}}{\large\to}\,\,\, {\ell\sin\pars{\braces{m - \ell}\pi/2} \over 2^{\ell - 1}\pars{m - \ell}} \int_{0}^{1}y^{m - \ell + 1}\pars{1 - y^{2}}^{\ell - 1}\,\dd y \\[5mm] & = {\ell\sin\pars{\braces{m - \ell}\pi/2} \over 2^{\ell}\pars{m - \ell}} \int_{0}^{1}y^{m/2 - \ell/2}\,\pars{1 - y}^{\ell - 1}\,\dd y \\[5mm] & = {\ell\sin\pars{\bracks{m - \ell}\pi/2} \over 2^{\ell}\pars{m - \ell}}\, {\Gamma\pars{m/2 - \ell/2 + 1}\Gamma\pars{\ell} \over \Gamma\pars{m/2 + \ell/2 + 1}} \\[5mm] & = {\ell\sin\pars{\bracks{m - \ell}\pi/2} \over 2^{\ell}\pars{m - \ell}}\, {\Gamma\pars{\ell} \over \Gamma\pars{m/2 + \ell/2 + 1}}\, {\pi \over \sin\pars{\pi\bracks{\ell/2 - m/2}}\Gamma\pars{\ell/2 - m/2}} \end{align} Then, \begin{align} I_{\ell,m} & \equiv \Re\int_{0}^{\pi/2}\cos^{\ell}\pars{\theta} \expo{\ic m\theta}\dd\theta = \bbx{\large{\pi \over 2^{\ell + 1}}{\ell \choose m/2 + \ell/2}} \label{3}\tag{3} \\ & \end{align}

---

With (\ref{2}) and (\ref{3}): \begin{align} &\bbox[4px,#ffd]{\sum_{j = 0}^{k}{k \choose j}{j/2 \choose n} \pars{-1}^{n + k - j}} = {\pars{-1}^{k} \over \pi}\,\bracks{n \geq k} \pars{I_{2n - k - 1,1 - k} - I_{2n - k - 1,1 + k}} \\[5mm] = &\ {\pars{-1}^{k} \over \pi}\bracks{n \geq k}\bracks{% {\pi \over 2^{2n - k}}{2n - k - 1 \choose n - k} - {\pi \over 2^{2n - k}}{2n - k - 1 \choose n}} \\[5mm] = &\ {\pars{-1}^{k} \over 2^{2n - k}}\bracks{n \geq k}\bracks{% {2n - k - 1 \choose n - 1} - {2n - k - 1 \choose n}} \\[5mm] = &\ {\pars{-1}^{k} \over 2^{2n - k}}\bracks{n \geq k}\braces{% {2n - k - 1 \choose n - 1} - {1 \over n}\bracks{{\pars{2n - k - 1} \over \pars{n - 1}! \pars{n - k}!}}\pars{n - k}} \\[5mm] \implies &\ \bbox[15px,#ffd,border:2px groove navy]{% \sum_{j = 0}^{k}{k \choose j}{j/2 \choose n}\pars{-1}^{n + k - j} = \bracks{n \geq k}{\pars{-1}^{k} \over 2^{2n - k}}\,{k \over n} {2n - k - 1 \choose n - 1}} \\ & \end{align}