Prove that $\sum\limits_{j=k}^n\,(-1)^{j-k}\,\binom{j}{k}\,\binom{2n-j}{j}\,2^{2(n-j)}=\binom{2n+1}{2k+1}$. In an attempt to answer this thread, I discovered an identity involving binomial coefficients.  However, I am not able to find a proof.  All tricks are welcome.

Let $n$ and $k$ be nonnegative integers with $k\leq n$.  Prove that $$\sum\limits_{j=k}^n\,(-1)^{j-k}\,\binom{j}{k}\,\binom{2n-j}{j}\,2^{2(n-j)}=\binom{2n+1}{2k+1}\,.$$

 A: Suppose we seek to show that
$$\sum_{q=k}^n (-1)^{q-k} {q\choose k} {2n-q\choose q}
2^{2(n-q)} = {2n+1\choose 2k+1}.$$
Re-index to get
$$\sum_{q=0}^{n-k} (-1)^{q} {q+k\choose k} {2n-k-q\choose k+q}
2^{2(n-k-q)}.$$
Introduce
$${2n-k-q\choose k+q}
= \frac{1}{2\pi i} 
\int_{|z|=\epsilon}
\frac{1}{z^{2n-2k-2q+1}} \frac{1}{(1-z)^{k+q+1}}
\; dz.$$
Observe  that this  vanishes  when  $q\gt n-k$  so  it provides  range
control and we may extend $q$ to infinity, getting for the sum
$$\frac{1}{2\pi i} 
\int_{|z|=\epsilon}
\frac{1}{z^{2n-2k+1}} \frac{1}{(1-z)^{k+1}}
\sum_{q\ge 0} (-1)^q {q+k\choose q} 
\frac{z^{2q}}{(1-z)^q} 2^{2(n-k-q)}
\; dz
\\ = \frac{2^{2(n-k)}}{2\pi i} 
\int_{|z|=\epsilon}
\frac{1}{z^{2n-2k+1}} \frac{1}{(1-z)^{k+1}}
\frac{1}{(1+z^2/(1-z)/2^2)^{k+1}}
\; dz
\\ = \frac{2^{2(n-k)}}{2\pi i} 
\int_{|z|=\epsilon}
\frac{1}{z^{2n-2k+1}} 
\frac{1}{(1-z+z^2/2^2)^{k+1}}
\; dz
\\ = \frac{2^{2n+2}}{2\pi i} 
\int_{|z|=\epsilon}
\frac{1}{z^{2n-2k+1}} 
\frac{1}{(4-4z+z^2)^{k+1}}
\; dz
\\ = \frac{2^{2n+2}}{2\pi i} 
\int_{|z|=\epsilon}
\frac{1}{z^{2n-2k+1}} 
\frac{1}{(z-2)^{2k+2}}
\; dz
\\ = \frac{2^{2n-2k}}{2\pi i} 
\int_{|z|=\epsilon}
\frac{1}{z^{2n-2k+1}} 
\frac{1}{(z/2-1)^{2k+2}}
\; dz
\\ = \frac{(-1)^{2k+2} 2^{2n-2k}}{2\pi i} 
\int_{|z|=\epsilon}
\frac{1}{z^{2n-2k+1}} 
\frac{1}{(1-z/2)^{2k+2}}
\; dz.$$
This is
$$2^{2n-2k} [z^{2n-2k}] \frac{1}{(1-z/2)^{2k+2}}
= 2^{2n-2k} {2n-2k+2k+1\choose 2k+1} \frac{1}{2^{2n-2k}}
\\ = {2n+1\choose 2k+1}$$
which is the claim.
Remark. We  discover having reached the end  of the computation
that we never needed to substitute the variable in the integral, which
means  it   could  be   done  using  formal   power  series   and  the
coefficient-of method.
Remark II. For the geometric series to converge we need with $\epsilon\ll 1$ (pole at $z=1$) that $|z^2/(1-z)/4| \lt 1$ which requires $\epsilon^2/(1-\epsilon)/4\lt 1.$ With $\epsilon = 1/Q$ this is $1/Q/(Q-1)/4\lt 1$ which is seen to hold for $Q\ge 2.$
A: It's convenient to use the coefficient of operator $[z^j]$ to denote the coefficient of $z^j$ in a series. This way we can write e.g.
\begin{align*}
[z^j](1+z)^n=\binom{n}{j}
\end{align*}

We recall the Euler transformation formula of a series
  \begin{align*}
A(z)=\sum_{n=  0}^\infty a_nz^n\qquad\qquad 
\frac{1}{1-z}A\left(\frac{z}{1-z}\right)=\sum_{n= 0}^\infty \left(\sum_{j=0}^n\binom{n}{j}a_j\right)z^n
\end{align*}
  This transformation formula together with a proof can be found e.g.  in Harmonic Number Identities Via Euler's transform by K.N. Boyadzhiev.
This  formula is useful, but it can be considerably generalized
\begin{align*}
\text{from}&\qquad&\sum_{j=0}^n\binom{n}{j}a_j&=[z^n]\frac{1}{1-z}A\left(\frac{z}{1-z}\right)\\
\text{to}&\qquad&\sum_{j=0}^n\binom{n+pj}{m+qj}a_j&=[z^n]\frac{z^m}{(1-z)^{m+1}}A\left(\frac{z^{q-p}}{(1-z)^q}\right)\qquad q>p\tag{1}
\end{align*}
A proof of (1) can be found in Theorem 2.1 in Riordan arrays and combinatorial sums by R. Sprugnoli.

We can now show:

The following is valid
  \begin{align*}
\sum_{j=k}^n(-1)^{j-k}\binom{j}{k}\binom{2n-j}{j}2^{2(n-j)}=\binom{2n+1}{2k+1}\tag{2}
\end{align*}

$$ $$

We start by rearranging the left hand side of (2)
  \begin{align*}
\sum_{j=k}^n&(-1)^{j-k}\binom{j}{k}\binom{2n-j}{j}2^{2(n-j)}\\
&=(-1)^k4^n\sum_{j=k}^n\binom{2n-j}{j}\binom{j}{k}\left(-\frac{1}{4}\right)^j\tag{3}
\end{align*}
In order to use (1) we derive a generating function $A(z)$ for 
  \begin{align*}
a_j=\binom{j}{k}\left(-\frac{1}{4}\right)^j
\end{align*}
  We obtain
  \begin{align*}
A(z)&=\sum_{j= 0}^\infty a_jz^j\\
&=\sum_{j=k}^\infty\binom{j}{k}\left(-\frac{1}{4}\right)^jz^j\\
&=\sum_{j=0}^\infty\binom{j+k}{j}\left(-\frac{1}{4}\right)^{j+k}z^{j+k}\tag{4}\\
&=\left(-\frac{z}{4}\right)^k\sum_{j=0}^\infty\binom{-k-1}{j}\left(\frac{z}{4}\right)^{j}\tag{5}\\
&=\frac{\left(-\frac{z}{4}\right)^k}{\left(1+\frac{z}{4}\right)^{k+1}}\tag{6}
\end{align*}

Comment:


*

*In (4) we shift the index so that $j$ starts from $0$.

*In (5) we apply the binomial identity $\binom{-u}{v}=\binom{u+v-1}{v}(-1)^v$.

*In (6) we apply the  binomial series expansion.
Since we have derived $A(z)$ we can proceed with the main calculation.

We obtain from (3) and (6)
  \begin{align*}
(-1)^k4^n&\sum_{j=k}^n\binom{2n-j}{j}\binom{j}{k}\left(-\frac{1}{4}\right)^{j}\\
&=(-1)^k4^n[z^{2n}]\frac{1}{1-z}A\left(\frac{z^2}{1-z}\right)\tag{7}\\
&=(-1)^k4^n[z^{2n}]\frac{1}{1-z}\left(-\frac{z^2}{4(1-z)}\right)^k\frac{1}{\left(1+\frac{z^2}{4(1-z)}\right)^{k+1}}\tag{8}\\
&=4^{n-k}[z^{2n-2k}]\frac{1}{\left(1-z+\frac{z^2}{4}\right)^{k+1}}\tag{9}\\
&=4^{n-k}[z^{2n-2k}]\frac{1}{\left(1-\frac{z}{2}\right)^{2(k+1)}}\\
&=4^{n-k}[z^{2n-2k}]\sum_{j=0}^\infty\binom{-2k-2}{j}\left(-\frac{z}{2}\right)^j\tag{10}\\
&=4^{n-k}[z^{2n-2k}]\sum_{j=0}^\infty\binom{2k+j-1}{j}\left(\frac{z}{2}\right)^j\tag{11}\\
&=4^{n-k}\binom{2n+1}{2n-2k}\frac{1}{4^{n-k}}\tag{12}\\
&=\binom{2n+1}{2k+1}
\end{align*}
  and the claim follows.

Comment:


*

*In (7) we use the representation (1) with the parameter settings
$
(n,m,p,q)\rightarrow (2n,0,-1,1)
$.

*In (8) we use the representation (6) of $A(z)$.

*In (9) we do some simplifications and use the rule $[z^{u+v}]A(z)=[z^u]z^{-v}A(z)$.

*In (10) we apply the binomial series expansion.

*In (11) we use the binomial identity $\binom{-u}{v}=\binom{u+v-1}{v}(-1)^v$.

*In (12) we select the coefficient of $z^{2n-2k}$.
A: I have found my own mostly combinatorial proof.  Write $[m]:=\{1,2,\ldots,m\}$ for every nonnegative integer $m$.  There are $\dbinom{2n+1}{2k+1}$ subsets $S$ of $[2n+1]$ of size $2k+1$.  We shall count the number of such sets given that the $(k+1)$-st largest element is $2n+1-s$ for some $s\in\{0,1,2,\ldots,2n\}$.  There are $k$ elements left to choose from $[2n-s]$, which can be done in $\dbinom{2n-s}{k}$ ways.  There are also $k$ elements to choose from $[2n+1]\setminus[2n+1-s]$, which can be done in $\dbinom{s}{k}$ ways.  Hence,
$$\binom{2n+1}{2k+1}=\sum_{s=0}^{2n}\,\binom{s}{k}\,\binom{2n-s}{k}=\sum_{s=k}^{2n-k}\,\binom{s}{k}\,\binom{2n-s}{k}\,.\tag{*}$$
Now, write $\dbinom{2n-s}{k}=\dbinom{2n-s}{s-(s-k)}$ for $s\geq k$.  Using the identity (2) from the answer here, which has a combinatorial proof, we obtain
$$\begin{align}
\dbinom{2n-s}{k}&=\sum_{r=0}^{s-k}\,(-1)^r\,\binom{s-k}{r}\,\binom{(2n-s)+(s-k)-r}{s}
\\&=\sum_{r=0}^{s-k}\,(-1)^r\,\binom{s-k}{r}\binom{2n-k-r}{s}\,.
\end{align}$$
Thus, (*) becomes
$$\binom{2n+1}{2k+1}=\sum_{s=k}^{2n-k}\,\binom{s}{k}\,\sum_{r=0}^{s-k}\,(-1)^r\,\binom{s-k}{r}\,\binom{2n-k-r}{s}\,.$$
Let $j:=r+k$.  We have
$$\binom{2n+1}{2k+1}=\sum_{j=k}^n\,(-1)^{j-k}\,\sum_{s=j}^{2n-k}\,\binom{s}{k}\,\binom{s-k}{j-k}\,\binom{2n-j}{s}\,.$$
Note that $\dbinom{s}{k}\,\dbinom{s-k}{j-k}=\dbinom{s}{j}\,\dbinom{j}{k}$.  Ergo,
$$\binom{2n+1}{2k+1}=\sum_{j=k}^n\,(-1)^{j-k}\,\binom{j}{k}\,\sum_{s=j}^{2n-k}\,\binom{s}{j}\,\binom{2n-j}{s}\,.$$
Again, we have $\dbinom{s}{j}\,\dbinom{2n-j}{s}=\dbinom{2n-j}{j}\,\dbinom{2(n-j)}{s-j}$, whence
$$\binom{2n+1}{2k+1}=\sum_{j=k}^n\,(-1)^{j-k}\,\binom{j}{k}\,\dbinom{2n-j}{j}\,\sum_{s=j}^{2n-k}\,\binom{2(n-j)}{s-j}\,.$$
Finally, $\sum\limits_{s=j}^{2n-k}\,\dbinom{2(n-j)}{s-j}=\sum\limits_{s=j}^{2n-j}\,\dbinom{2(n-j)}{s-j}=2^{2(n-j)}$ leads to
$$\binom{2n+1}{2k+1}=\sum_{j=k}^n\,(-1)^{j-k}\,\binom{j}{k}\,\dbinom{2n-j}{j}\,2^{2(n-j)}\,.$$
A: Here is another variation of the theme. It is convenient to use the coefficient of operator $[z^j]$ to denote the coefficient of $z^j$ in a series. This way we can write e.g.
\begin{align*}
[z^j](1+z)^n=\binom{n}{j}
\end{align*}

We obtain
  \begin{align*}
\sum_{q=k}^n&(-1)^{q-k}\binom{q}{k}\binom{2n-q}{q}4^{n-q}\\
&=\sum_{q=0}^{n-k}(-1)^q\binom{k+q}{q}\binom{2n-k-q}{k+q}4^{n-k-q}\tag{1}\\
&=\sum_{q=0}^{n-k}\binom{-k-1}{q}\binom{-(k+q+1)}{2n-2k-2q}4^{n-k-q}\tag{2}\\
&=\sum_{q=0}^\infty[z^q](1+z)^{-(k+1)}[u^{2n-2k-2q}](1+u)^{-(k+q+1)}4^{n-k-q}\tag{3}\\
&=4^{n-k}[u^{2n-2k}](1+u)^{-(k+1)}\sum_{q=0}^\infty\left(\frac{u^2}{4(1+u)}\right)^q[z^q](1+z)^{-(k+1)}\tag{4}\\
&=4^{n-k}[u^{2n-2k}](1+u)^{-(k+1)}\left(1+\frac{u^2}{4(1+u)}\right)^{-(k+1)}\tag{5}\\
&=4^{n-k}[u^{2n-2k}]\left(1+\frac{u}{2}\right)^{-2(k+1)}\tag{6}\\
&=4^{n-k}[u^{2n-2k}]\sum_{q=0}^{\infty}\binom{-2k-2}{q}\left(\frac{u}{2}\right)^q\tag{7}\\
&=4^{n-k}[u^{2n-2k}]\sum_{q=0}^{\infty}\binom{2k+q+1}{q}\left(-\frac{u}{2}\right)^q\tag{8}\\
&=\binom{2n+1}{2n-2k}\tag{9}\\
&=\binom{2n+1}{2k+1}
\end{align*}
  and the claim follows.

Comment:


*

*In (1) we shift the index $q$ to start from $0$.

*In (2) we use the binomial identity $\binom{-p}{q}=\binom{p+q-1}{q}(-1)^q$.

*In (3) we apply the coefficient of operator twice and we extend the upper limit of the sum to $\infty$ without changing anything, since we are adding zeros only.

*In (4) we use the linearity of the coefficient of operator and apply the rule $[z^{p-q}]A(z)=[z^p]z^qA(z)$.

*In (5) we use the substitution rule with $z=\frac{u^2}{4(1+u)}$
\begin{align*}
A(u)=\sum_{q=0}^\infty a_qu^q=\sum_{q=0}^\infty u^q[z^q]A(z)\\
\end{align*}

*In (6) we do some simplifications.

*In (7) we apply the binomial series expansion.

*In (8) we use again the binomial identity as in (2).

*In (9) we select the coefficient of $u^{2n-2k}$.
