Binomial sums from Bieberbach conjecture It seems that I need some kind of hint or help with Exercise 33 from this wonderful blog post by T. Tao, namely with the following equality:
$$
\sum_{j=0}^{n - k} (-1)^j {2k + 2j \choose j} {n + j + k + 1 \choose n - k - j} = \frac{1 + (-1)^{n - k}}{2},
$$
for all $n \geq 1$ and $0 \leq k \leq n$. It must be some easy exercise since no hints provided, but I still have no ideas though I had already tried to use some induction or straightforward counting. 
Any help appreciated. Thanks in advance.
 A: Here is a starter. We show the claim is valid for the special case $k=0$.
\begin{align*}
\sum_{j=0}^n(-1)^j\binom{2j}{j}\binom{n+j+1}{n-j}=\frac{1}{2}\left(1+(-1)^n\right)\qquad\qquad n\geq 0
\end{align*}
It is convenient to use the coefficient of operator $[z^k]$ to denote the coefficient of $z^k$ of a series. This way we can write for instance
\begin{align*}
[z^k](1+z)^n=\binom{n}{k}
\end{align*}

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

Comment:


*

*In (1) we use the binomial identity $\binom{-\frac{1}{2}}{j}=\left(-\frac{1}{4}\right)^j\binom{2j}{j}$.

*In (2) we apply the coefficient of operator twice and set the upper limit of the series to $\infty$ without changing anything since we are adding zeros only.

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

*In (4) we apply the substitution rule of the coefficient of operator with $z=4u(1+u)$
\begin{align*}
A(u)=\sum_{j=0}^\infty a_j u^j=\sum_{j=0}^\infty u^j [z^j]A(z)
\end{align*}

*In (5) we apply the geometric series expansion.

*In (6) we apply the rules as in (3) and we set the upper limit of the sum to $n$ since other values do not contribute.

*In (7) we change the order of summation $j\to n-j$.

*In (8) we select the coefficient of $u^j$.

*In (9) we apply the binomial theorem.
A: It is convenient to use the coefficient of operator $[z^k]$ to denote the coefficient of $z^k$ of a series. This way we can write for instance
\begin{align*}
[z^k](1+z)^n=\binom{n}{k}
\end{align*}

We obtain for integral $0\leq k\leq n$:
  \begin{align*}
&\color{blue}{\sum_{j=0}^n}\color{blue}{(-1)^j\binom{2j+2k}{j}\binom{n+k+j+1}{n-k-j}}\\
&\ \,=\sum_{j=k}^n(-1)^{j+k}\binom{2j}{j-k}\binom{n+j+1}{n-j}\tag{1}\\
&\ \,=\sum_{j=0}^\infty(-1)^{j+k}[z^j]\frac{1}{\sqrt{1-4z}}\left(\frac{1-2z-\sqrt{1-4z}}{2z}\right)^k[u^{n-j}](1+u)^{n+j+1}\tag{2}\\
&\ \,=(-1)^k[u^n](1+u)^{n+1}\sum_{j=0}^\infty\left(-u(1+u)\right)^j[z^j]\frac{1}{\sqrt{1-4z}}\left(\frac{1-2z-\sqrt{1-4z}}{2z}\right)^k\tag{3}\\
&\ \,=(-1)^k[u^n](1+u)^{n+1}\frac{1}{\sqrt{1+4u(1+u)}}\\
&\qquad\qquad\qquad\qquad\qquad\qquad\qquad\cdot\left(\frac{1+2u(1+u)-\sqrt{1+4u(1+u)}}{-2u(1+u)}\right)^k\tag{4}\\
&\ \,=(-1)^k[u^n](1+u)^{n+1}\frac{1}{1+2u}\left(-\frac{u}{1+u}\right)^k\tag{5}\\
&\ \,=[u^{n-k}]\sum_{j=0}^\infty (-2u)^j(1+u)^{n-k+1}\tag{6}\\
&\ \,=\sum_{j=0}^{n-k}(-2)^j[u^{n-k-j}](1+u)^{n-k+1}\tag{7}\\
&\ \,=\sum_{j=0}^{n-k}(-2)^{n-k-j}[u^j](1+u)^{n-k+1}\tag{8}\\
&\ \,=\sum_{j=0}^{n-k}\binom{n-k+1}{j}(-2)^{n-k-j}\tag{9}\\
&\ \,=-\frac{1}{2}\left((1-2)^{n-k+1}-1\right)\tag{10}\\
&\ \,=\color{blue}{\frac{1}{2}\left(1+(-1)^{n-k}\right)}
\end{align*}
  and the claim follows.

Comment:


*

*In (1) we shift the summation index to start with $j=k$.

*In (2) we apply the coefficient of operator twice and set the index range from $0$ to $\infty$ without changing anything since we are adding zeros only. Here  we  use a cousin of the generating function  of the central binomial coefficient 
\begin{align*}
\sum_{m=0}^\infty\binom{2m}{m}z^m&=\frac{1}{\sqrt{1-4z}}\\
\sum_{m=0}^\infty\binom{2m}{m-k}z^m&=\frac{1}{\sqrt{1-4z}}\left(\frac{1-2z-\sqrt{1-4z}}{2z}\right)^k
\end{align*}

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

*In (4) we apply the substitution rule of the coefficient of operator with $z=-u(1+u)$
\begin{align*}
A(u)=\sum_{j=0}^\infty a_j u^j=\sum_{j=0}^\infty u^j [z^j]A(z)
\end{align*}

*In (5) we do some simplifications.

*In (6) we apply the geometric series expansion.

*In (7) we apply the rules as in (3) and we set the upper limit of the sum to $n-k$ since other values do not contribute.

*In (8) we change the order of summation $j\to n-k-j$.

*In (9) we select the coefficient of $u^j$.

*In (10) we apply the binomial theorem.
