<s>[INST] Binomial Identity with strange coefficients In my work, I have come across the following equation
$$ \sum_{k = 0}^m \sum_{l = 0}^{n-m} {m \choose k} {n - m \choose l} (-1)^k r_{k + l} $$
where $r_n = 1$ if $n$ is congruent to 0 or 1 modulo 4, and $r_n = -1$ if $n$ is congruent to 2 or 3 modulo 4. I've seen some identities involving the products ${m \choose k} {n - m \choose l}$, but I can't seem to find an algebraic trick to reduce this form to a standard identity. Any tips?
 [/INST] This is
$$\sum_{k=0}^m {m\choose k} (-1)^k
\sum_{l=0}^{n-m} {n-m\choose l} r_{k+l}.$$
We have that
$$r_{k+l} =
\frac{1}{2\pi i}
\int_{|w|=\gamma}
\frac{1}{w^{k+l+1}} (1+w - w^2-w^3 + \cdots)
\; dw
\\ = \frac{1}{2\pi i}
\int_{|w|=\gamma}
\frac{1}{w^{k+l+1}} 
\frac{1+w - w^2-w^3}{1-w^4}
\; dw.$$
We get for the sum
$$\frac{1}{2\pi i}
\int_{|w|=\gamma}
\frac{1}{w}
\frac{1+w - w^2-w^3}{1-w^4}
\sum_{k=0}^m {m\choose k} \frac{(-1)^k}{w^k}
\sum_{l=0}^{n-m} {n-m\choose l} \frac{1}{w^l}
\; dw
\\ = 
\frac{1}{2\pi i}
\int_{|w|=\gamma}
\frac{1}{w}
\frac{1+w - w^2-w^3}{1-w^4}
\sum_{k=0}^m {m\choose k} \frac{(-1)^k}{w^k}
\left(1+\frac{1}{w}\right)^{n-m}
\; dw
\\ = \frac{1}{2\pi i}
\int_{|w|=\gamma}
\frac{(1+w)^{n-m}}{w^{n-m+1}}
\frac{1+w - w^2-w^3}{1-w^4}
\sum_{k=0}^m {m\choose k} \frac{(-1)^k}{w^k}
\; dw
\\ = \frac{1}{2\pi i}
\int_{|w|=\gamma}
\frac{(1+w)^{n-m}}{w^{n-m+1}}
\frac{1+w - w^2-w^3}{1-w^4}
\left(1-\frac{1}{w}\right)^m
\; dw
\\ = \frac{1}{2\pi i}
\int_{|w|=\gamma}
\frac{(1+w)^{n-m} (w-1)^m}{w^{n+1}}
\frac{1+w - w^2-w^3}{1-w^4}
\; dw
\\ = \frac{1}{2\pi i}
\int_{|w|=\gamma}
\frac{(1+w)^{n-m} (w-1)^m}{w^{n+1}}
\frac{1+w}{1+w^2}
\; dw
\\ = \frac{1}{2\pi i}
\int_{|w|=\gamma}
\frac{(1+w)^{n-m+1} (w-1)^m}{w^{n+1}}
\frac{1}{1+w^2}
\; dw.$$
Now  checking on  the residue  at infinity  by a  circular contour  of
radius   $R$   we   obtain   a   term  of   order   $2\pi   R   \times
R^{n+1}/R^{n+1}/R^2$ which is $2\pi/R$ and vanishes so that residue is
zero. This  leaves for the  sum the residues at  $w=\pm i$ and  we get
(remember to flip the sign at the end)
$$\exp(-(n+1)\pi i/2)
\sqrt{2}^{n+1} \frac{1}{2i} \exp(+(n-m+1)\pi i/4)\exp(+3m\pi i/4) \\
- \exp(+(n+1)\pi i/2) 
\sqrt{2}^{n+1} \frac{1}{2i} \exp(-(n-m+1)\pi i/4)\exp(-3m\pi i/4)
\\ = \sqrt{2}^{n+1} \sin(-(2n+2)\pi/4 +(n-m+1)\pi/4 + 3m\pi/4).$$
This yields $$- \sqrt{2}^{n+1} \sin((2m-n-1)\pi/4)$$ or
$$\bbox[5px,border:2px solid #00A000]{
\sqrt{2}^{n+1} \sin((n+1-2m)\pi/4).}$$
</s>