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}\,.$$
On
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}$.
On
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)}\,.$$
On
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}$.
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.$
Addendum Aug 23. Here is an alternate answer. We seek to prove that with $n\ge 1$ and $1\lt k \le n$
$$\sum_{q=k}^n 2^{2n-2q} (-1)^{q+k} {2n-q\choose 2n-2q} {q\choose k} = {2n+1\choose 2k+1}.$$
We re-write the sum to start
$$2^{2n-2k} \sum_{q=0}^{n-k} 2^{-2q} (-1)^{q} {2n-k-q\choose 2n-2k-2q} {q+k\choose k}.$$
Continuing,
$$2^{2n-2k} [z^{2n-2k}] (1+z)^{2n-k} \sum_{q\ge 0} 2^{-2q} (-1)^{q} (1+z)^{-q} z^{2q} {q+k\choose k}.$$
Here we have extended to infinity due to the coefficient extractor. Moving along,
$$2^{2n-2k} [z^{2n-2k}] (1+z)^{2n-k} \frac{1}{(1+z^2/(1+z)/4)^{k+1}} \\ = 2^{2n-2k} [z^{2n-2k}] (1+z)^{2n-k} \frac{(1+z)^{k+1} 2^{2k+2}}{(4+4z+z^2)^{k+1}} \\ = 2^{2n+2} [z^{2n-2k}] (1+z)^{2n+1} \frac{1}{(z+2)^{2k+2}}.$$
This is
$$2^{2n+2} \; \underset{z}{\mathrm{res}} \; \frac{1}{z^{2n+1-2k}} (1+z)^{2n+1} \frac{1}{(z+2)^{2k+2}}.$$
Now put $z/(1+z)=w$ so that $z=w/(1-w)$ and $dz = 1/(1-w)^2 \; dw$ to get
$$2^{2n+2} \; \underset{w}{\mathrm{res}} \; \frac{1}{w^{2n+1}} \frac{w^{2k}}{(1-w)^{2k}} \frac{(1-w)^{2k+2}}{(2-w)^{2k+2}} \frac{1}{(1-w)^2} \\ = 2^{2n+2} \; \underset{w}{\mathrm{res}} \; \frac{1}{w^{2n+1-2k}} \frac{1}{(2-w)^{2k+2}} \\ = 2^{2n-2k} \; \underset{w}{\mathrm{res}} \; \frac{1}{w^{2n+1-2k}} \frac{1}{(1-w/2)^{2k+2}} \\ = 2^{2n-2k} {2n-2k+2k+1\choose 2k+1} 2^{-(2n-2k)} = {2n+1\choose 2k+1}.$$
We again have the claim.