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.
On
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.
On
Starting from (here evidently $n\ge k$ for it to be meaningful).
$$\sum_{j=0}^{n-k} (-1)^j {2k+2j\choose j} {n+k+j+1\choose n-k-j} \\ = (-1)^{n-k} \sum_{j=0}^{n-k} (-1)^j {2n-2j\choose n-k-j} {2n-j+1\choose j} \\ = (-1)^{n-k} \sum_{j=0}^{n-k} (-1)^j {2n-2j\choose n-k-j} {2n+1-j\choose 2n+1-2j}.$$
we write
$$(-1)^{n-k} \sum_{j=0}^{n-k} (-1)^j {2n+1-j\choose 2n+1-2j} [z^{n-k-j}] (1+z)^{2n-2j} \\ = (-1)^{n-k} [z^{n-k}] (1+z)^{2n} \sum_{j=0}^{n-k} (-1)^j {2n+1-j\choose 2n+1-2j} z^j (1+z)^{-2j}$$
We get no contribution to the coefficient extractor when $j\gt n-k$ and hence may continue with
$$(-1)^{n-k} [z^{n-k}] (1+z)^{2n} \sum_{j\ge 0} (-1)^j {2n+1-j\choose 2n+1-2j} z^j (1+z)^{-2j} \\ = (-1)^{n-k} [z^{n-k}] (1+z)^{2n} \sum_{j\ge 0} (-1)^j z^j (1+z)^{-2j} [w^{2n+1-2j}] (1+w)^{2n+1-j} \\ = (-1)^{n-k} [z^{n-k}] (1+z)^{2n} [w^{2n+1}] (1+w)^{2n+1} \sum_{j\ge 0} (-1)^j z^j (1+z)^{-2j} w^{2j} (1+w)^{-j} \\ = (-1)^{n-k} [z^{n-k}] (1+z)^{2n} [w^{2n+1}] (1+w)^{2n+1} \frac{1}{1 + z w^2 / (1+z)^2 / (1+w)} \\ = (-1)^{n-k} [z^{n-k}] (1+z)^{2n+2} [w^{2n+1}] (1+w)^{2n+2} \frac{1}{(1+z)^2(1+w) + z w^2} \\ = (-1)^{n-k} [z^{n-k}] (1+z)^{2n+2} [w^{2n+1}] (1+w)^{2n+2} \frac{1}{(w+1+z)(wz+1+z)} \\ = (-1)^{n-k} [z^{n+1-k}] (1+z)^{2n+2} [w^{2n+1}] (1+w)^{2n+2} \frac{1}{(w+1+z)(w+(1+z)/z)}.$$
Now the inner term is
$$\mathrm{Res}_{w=0} \frac{1}{w^{2n+2}} (1+w)^{2n+2} \frac{1}{(w+1+z)(w+(1+z)/z)}.$$
Residues sum to zero and the residue at infinity is zero since $\lim_{R\rightarrow\infty} 2\pi R \times R^{2n+2} / R^{2n+2} /R^2 = 0.$ Hence we may compute this from minus the sum of the residues at $-(1+z)$ and $-(1+z)/z.$ The first one yields
$$-\frac{1}{(1+z)^{2n+2}} z^{2n+2} \frac{1}{-(1+z)+(1+z)/z}.$$
Replace this in the remaining coefficient extractor to get
$$(-1)^{n+1-k} [z^{n+1-k}] z^{2n+3} \frac{1}{1-z^2} = 0.$$
The second one yields
$$- \frac{z^{2n+2}}{(1+z)^{2n+2}} \frac{1}{z^{2n+2}} \frac{1}{-(1+z)/z+1+z}$$
Once more replace this in the remaining coefficient extractor to get
$$(-1)^{n+1-k} [z^{n+1-k}] \frac{1}{-(1+z)/z+1+z} = (-1)^{n+1-k} [z^{n+1-k}] \frac{z}{z^2-1} \\ = - [z^{n+1-k}] \frac{z}{z^2-1} = [z^{n-k}] \frac{1}{1-z^2}.$$
This is
$$\bbox[5px,border:2px solid #00A000]{ [[(n-k) \;\text{is even}]] = \frac{1+(-1)^{n-k}}{2}}$$
as claimed.
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*}
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.