[Math] A Binomial Coefficient Sum: $\sum_{m = 0}^{n} (-1)^{n-m} \binom{n}{m} \binom{m-1}{l}$

binomial-coefficientscombinatoricssummation

In my work on $f$-vectors in polytopes, I ran across an interesting sum which has resisted all attempts of algebraic simplification. Does the following binomial coefficient sum simplify?
\begin{align}
\sum_{m = 0}^{n} (-1)^{n-m} \binom{n}{m} \binom{m-1}{l} \qquad l \geq 0
\end{align}
Update: After some numerical work, I believe a binomial sum orthogonality identity is at work here because I see only $\pm 1$ and zeros. Any help would certainly be appreciated.

I take $\binom{-1}{l} = (-1)^{l}$, $\binom{m-1}{l} = 0$ for $0 < m < l$ and the standard definition otherwise.

Thanks!

Best Answer

This is a special case of the identity $$\sum_k \binom{l}{m+k} \binom{s+k}{n} (-1)^k = (-1)^{l+m} \binom{s-m}{n-l},$$ which is identity 5.24 on p. 169 of Concrete Mathematics, 2nd edition. With $l = n$, $m = 0$, $s = -1$, $k = m$, and $n = l$, we see that the OP's sum is $$(-1)^{2n} \binom{-1}{l-n} = \binom{-1}{l-n}.$$ This is $(-1)^{l-n}$ when $l \geq n$ and $0$ when $l < n$, as in Fabian's comment to Plop's answer.

Related Question