I am trying to perform the sum
\begin{equation}
\sum_{k=0}^n2^k\binom{2(n+1-j)}{k}\binom{-n-1}{n-k}.
\end{equation}
According to Mathematica the result is
\begin{equation}
\frac{4^n(n-j+1/2)!}{n!(1/2-j)!},
\end{equation}
which we can also write as
\begin{equation}
4^n\binom{n-j+1/2}{n}.
\end{equation}
I am having trouble proving this result. If it weren't for the $2^k$ in the summand, we could use the Chu-Vandermonde identity
\begin{equation}
\sum_{k=0}^n\binom{m}{k}\binom{p}{n-k}=\binom{m+p}{n}.
\end{equation}
I think the Legendre duplication formula
\begin{equation}
\Gamma(z)\Gamma(z+1/2)=2^{1-2z}\sqrt{\pi}\Gamma(2z)
\end{equation}
might be helpful in removing the $2^k$, but I have not been able to get that to work either.
I would be grateful for any suggestions to help me match the Mathematica output.
Best Answer
We seek to prove that
$$\sum_{k=0}^n 2^k {2n+2-2j\choose k} {-n-1\choose n-k} = 4^n {n-j+1/2\choose n}.$$
The LHS is
$$[z^n] (1+z)^{-n-1} \sum_{k\ge 0} 2^k {2n+2-2j\choose k} z^k.$$
Here we have extended the range to infinity because the coefficient extractor enforces the upper limit. Continuing,
$$[z^n] (1+z)^{-n-1} (1+2z)^{2n+2-2j}.$$
which also follows by inspection. This is
$$\;\underset{z}{\mathrm{res}}\; \frac{1}{z^{n+1}} \frac{1}{(1+z)^{n+1}} (1+2z)^{2n+2-2j}.$$
Now we put $z=(-1+\sqrt{1+4w})/2$ so that $z(1+z)=w$ and $dz = 1/\sqrt{1+4w} \; dw$ to get
$$\;\underset{w}{\mathrm{res}}\; \frac{1}{w^{n+1}} \sqrt{1+4w}^{2n+2-2j} \frac{1}{\sqrt{1+4w}} \\ = \;\underset{w}{\mathrm{res}}\; \frac{1}{w^{n+1}} (1+4w)^{n-j+1/2} = 4^n {n-j+1/2\choose n}.$$