Proving $\sum_{i=0}^K(-1)^i\binom{2n+1-i}{i}\binom{2n-2i}{K-i}=\frac{1}{2}(1+(-1)^K)$ I encountered the following binomial equality:
$$\sum_{i=0}^K(-1)^i\binom{2n+1-i}{i}\binom{2n-2i}{K-i}=\frac{1}{2}(1+(-1)^K)$$
which I know it's true, but I don't know how to prove it directly. I entered the left-hand-side to Mathematica, and it directly gave me the right-hand-side. So I wonder if anyone knows an elementary proof.
 A: We seek to show that
$$\sum_{q=0}^K (-1)^q {2n+1-q\choose q}
{2n-2q\choose K-q} = \frac{1}{2} (1+(-1)^K).$$
The LHS is
$$\frac{1}{2\pi i} \int_{|w|=\gamma}
\frac{1}{2\pi i} \int_{|z|=\varepsilon}
\sum_{q=0}^K
(-1)^q \frac{1}{z^{q+1}} (1+z)^{2n+1-q}
\frac{1}{w^{K-q+1}} (1+w)^{2n-2q}
\; dz \; dw
\\ = \frac{1}{2\pi i} \int_{|w|=\gamma}
\frac{1}{w^{K+1}} (1+w)^{2n}
\frac{1}{2\pi i} \int_{|z|=\varepsilon}
\frac{1}{z} (1+z)^{2n+1}
\\ \times
\sum_{q=0}^K
(-1)^q \frac{1}{z^q} (1+z)^{-q}
w^q (1+w)^{-2q}
\; dz \; dw.$$
Here we may extend $q$ beyond $K$ to infinity because the pole at zero
in $w$ is canceled for the extra values. We obtain
$$\frac{1}{2\pi i} \int_{|w|=\gamma}
\frac{1}{w^{K+1}} (1+w)^{2n}
\frac{1}{2\pi i} \int_{|z|=\varepsilon}
\frac{1}{z} (1+z)^{2n+1}
\\ \times
\frac{1}{1+w/(1+w)^2/z/(1+z)}
\; dz \; dw
\\ = \frac{1}{2\pi i} \int_{|w|=\gamma}
\frac{1}{w^{K+1}} (1+w)^{2n+2}
\frac{1}{2\pi i} \int_{|z|=\varepsilon}
(1+z)^{2n+2}
\\ \times
\frac{1}{(1+z(1+w))(w+z(1+w))}
\; dz \; dw.$$
The pole at zero in $z$ is gone but a new pole has appeared inside the
contour. Note that when we summed the geometric series we required
$|w/(1+w)^2| \lt |z(1+z)|.$ We have with $\gamma\ll 1$ and
$\varepsilon\ll 1$ that $|w/(1+w)^2| \le  \gamma/(1-\gamma)^2 \lt
2\gamma$ and $|z(1+z)| \ge \varepsilon (1-\varepsilon) \gt
\frac{1}{2}\varepsilon.$ Therefore  taking $\varepsilon = 4\gamma$ will
work e.g. $\gamma=1/11$ and  $\varepsilon = 4/11.$
We have for the first simple pole at  $z_0=-1/(1+w)$ that $|-1/(1+w)| \gt
1/(1+\gamma) \gt 4\gamma =  \varepsilon.$ This pole is not inside the
contour. The second pole is  at $z_1=-w/(1+w)$ and we have $|-w/(1+w)|
\lt \gamma/(1-\gamma) \lt  4\gamma = \varepsilon.$ This pole is inside
the contour. We thus write
$$\frac{1}{2\pi i} \int_{|w|=\gamma}
\frac{1}{w^{K+1}} (1+w)^{2n+1}
\frac{1}{2\pi i} \int_{|z|=\varepsilon}
(1+z)^{2n+2}
\\ \times
\frac{1}{(1+z(1+w))(w/(1+w)+z)}
\; dz \; dw.$$
Evaluating the residue from the simple pole at $z_1$ we find
$$\frac{1}{2\pi i} \int_{|w|=\gamma}
\frac{1}{w^{K+1}} (1+w)^{2n+1}
(1-w/(1+w))^{2n+2} \frac{1}{1-(1+w)w/(1+w)} \; dw
\\ = \frac{1}{2\pi i} \int_{|w|=\gamma}
\frac{1}{w^{K+1}} \frac{1}{1-w^2} \; dw.$$
This is
$$[w^K] \frac{1}{1-w^2} = \frac{1}{2}(1+(-1)^K)$$
as claimed.
A: Here is a starter. We transform the sum and separate one part which can be simplified. We start with the left hand side of OPs identity and obtain
\begin{align*}
\sum_{i=0}^K&(-1)^i\binom{2n+1-i}{i}\binom{2n-2i}{K-i}\\
&=\sum_{i=0}^K(-1)^i\frac{(2n+1-i)!}{i!(2n+1-2i)!}\,\frac{(2n-2i)!}{(K-i)!(2n-K-i)!}\\
&=\sum_{i=0}^K(-1)^i\binom{K}{i}\binom{2n-i}{K}\frac{2n+1-i}{2n+1-2i}\tag{1}\\
\end{align*}

With (1) we can reformulate OPs claim for $0\leq K\leq 2n$ as
\begin{align*}
\color{blue}{\sum_{i=0}^K(-1)^i\binom{K}{i}\binom{2n-i}{K}\frac{2n+1-i}{2n+1-2i}=\frac{1}{2}\left(1+(-1)^K\right)}\tag{2}
\end{align*}

We can write the left-hand side of (2) as
\begin{align*}
\sum_{i=0}^K(-1)^i\binom{K}{i}\binom{2n-i}{K}\left(1+\frac{i}{2n+1-2i}\right)\tag{3}
\end{align*}
In the following we use the coefficient of operator $[z^n]$ to denote the coefficient of $z^n$ of a series. This way we can write for instance
\begin{align*}
[z^p](1+z)^q=\binom{q}{p}\tag{4}
\end{align*}

We obtain from (3)
\begin{align*}
\color{blue}{\sum_{i=0}^K}&\color{blue}{(-1)^i\binom{K}{i}\binom{2n-i}{K}}\\
&=\sum_{i=0}^K(-1)^i\binom{K}{k}\binom{2n-i}{2n-i-K}\tag{5.1}\\
&=\sum_{i=0}^K(-1)^i\binom{K}{i}[z^{2n-i-K}](1+z)^{2n-i}\tag{5.2}\\
&=[z^{2n-K}](1+z)^{2n}\sum_{i=0}^K\binom{K}{i}\left(-\frac{z}{1+z}\right)^i\tag{5.3}\\
&=[z^{2n-k}](1+z)^{2n}\left(1-\frac{z}{1+z}\right)^K\tag{5.4}\\
&=[z^{2n-k}](1+z)^{2n-K}\\
&=\binom{2n-K}{2n-K}\\
&\,\,\color{blue}{=1}\tag{5.5}
\end{align*}

Comment:

*

*In (5.1) we use $\binom{p}{q}=\binom{p}{p-q}$.


*In (5.2) we use (3).


*In (5.3) we use $[z^{p-q}]A(z)=[z^p]z^qA(z)$.


*In (5.4) we apply the binomial theorem and do some simplifications in the following steps.

We also obtain from (3)
\begin{align*}
\color{blue}{\sum_{i=1}^K}&\color{blue}{(-1)^i\binom{K}{i}\binom{2n-i}{K}\frac{i}{2n+1-2i}}\\
&=K\sum_{i=1}^K(-1)^i\binom{K-1}{i-1}\binom{2n-i}{K}\frac{1}{2n+1-2i}\tag{6.1}\\
&=K\sum_{i=0}^{K-1}(-1)^{i+1}\binom{K-1}{i}\binom{2n-i-1}{K}\frac{1}{2n-1-2i}\tag{6.2}\\
&=K\sum_{i=0}^{K-1}(-1)^{i+1}\binom{K-1}{i}\binom{2n-i-1}{2n-i-1-K}\frac{1}{2n-1-2i}\tag{6.3}\\
&\color{blue}{=(-1)^KK\sum_{i=0}^{K-1}\binom{K-1}{i}\binom{-K-1}{2n-i-1-K}\frac{1}{2n-1-2i}}\tag{6.4}\\
\end{align*}

Comment:

*

*In (6.1) we use $\binom{p}{q}=\frac{p}{q}\binom{p-1}{q-1}$.


*In (6.2) we shift the index to start with $i=0$.


*In (6.3) we use $\binom{p}{q}=\binom{p}{p-q}$.


*In (6.4) we use $\binom{-p}{q}=\binom{p+q-1}{q}(-1)^q$.

We finally derive from (3), (5.5) and (6.4) the following claim
\begin{align*}
\color{blue}{K\sum_{i=0}^{K-1}\binom{K-1}{i}\binom{-K-1}{2n-i-1-K}\frac{1}{2n-1-2i}=\frac{1}{2}\left(1-(-1)^K\right)}
\end{align*}
which could alternatively be used to prove OPs claim.

