# A Binomial Coefficient Sum

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!

-
Does your summation begin from $m = l+1$? –  user17762 Apr 25 '11 at 17:55
Then I assume you need to interpret $\binom{n}{r} = 0$ when $n < r$? –  user17762 Apr 25 '11 at 17:57
Perhaps you could mention how it arose? –  mixedmath Apr 25 '11 at 17:57
No, the sum must start at $m = 0$. I interpret $\binom{-1}{l} = (-1)^{l}$. –  user02138 Apr 25 '11 at 18:01
@user: That is non-"standard", isn't it? Why don't you edit the question with what you mean by $\binom{n}{r}$ when $n \lt r$ (and not just for $n=-1$.)? –  Aryabhata Apr 25 '11 at 18:29

$$\sum_{m=0}^n (-1)^{n-m} \binom{n}{m} \binom{m-1}{l} = (-1)^{l+n} + \sum_{l+1 \leq m \leq n} (-1)^{n-m} \binom{n}{m} \binom{m-1}{l}$$ So we need to compute this last sum. It is clearly zero if $l \geq n$, so we assume $l < n$.

It is equal to $f(1)$ where $f(x)= \sum_{l+1 \leq m \leq n} (-1)^{n-m} \binom{n}{m} \binom{m-1}{l} x^{m-1-l}$. We have that $$\begin{eqnarray*} f(x) & = & \frac{1}{l!} \frac{d^l}{dx^l} \left( \sum_{l+1 \leq m \leq n} (-1)^{n-m} \binom{n}{m} x^{m-1} \right) \\ & = & \frac{1}{l!} \frac{d^l}{dx^l} \left( \frac{(-1)^{n+1}}{x} + \sum_{0 \leq m \leq n} (-1)^{n+1} \binom{n}{m} (-x)^{m-1} \right) \\ & = & \frac{1}{l!} \frac{d^l}{dx^l} \left( \frac{(-1)^{n+1}}{x} + \frac{(x-1)^n}{x} \right) \\ & = & \frac{(-1)^{n+1+l}}{x^{l+1}} + \frac{1}{l!} \sum_{k=0}^l \binom{l}{k} n(n-1) \ldots (n-k+1) (x-1)^{n-k} \frac{(-1)^{l-k} (l-k)!}{x^{1+l-k}} \end{eqnarray*}$$ (this last transformation thanks to Leibniz) and since $n>l$, $f(1)=(-1)^{l+n+1}$.

In the end, your sum is equal to $(-1)^{l+n}$ if $l \geq n$, $0$ otherwise.

-
choosing some values $l$ and $n$ and summing the series numerically, I seem to get 0 for $l<n$; $(-1)^{l+n}$ I only get for $l\geq n$... –  Fabian Apr 25 '11 at 18:38
You are right, I forgot a term. Corrected. –  Plop Apr 25 '11 at 18:57

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.

-
Thanks. Nice Addendum. –  user02138 Apr 25 '11 at 18:49
Great stuff! I'm far away from my copy of CM, and Google won't let me peek, so... is there a justification in the book? (If so, I'll look it up myself when I get to my library.) –  Ｊ. Ｍ. Apr 25 '11 at 18:56
I found a copy here –  user02138 Apr 25 '11 at 19:03
@J.M.: There is a derivation on p. 170 that uses induction. They also mention that "we can reduce it to Vandermonde's convolution by a sequence of transformations." –  Mike Spivey Apr 25 '11 at 19:59


\begin{align} &\color{#66f}{\large\sum_{m = 0}^{n}\pars{-1}^{n - m}{n \choose m} {m - 1 \choose \ell}} \\[3mm]&=\pars{-1}^{n}\sum_{m = 0}^{n}\pars{-1}^{m}{n \choose m} \oint_{0\ <\ \verts{z}\ =\ a\ <\ 1}{\pars{1 + z}^{m - 1} \over z^{\ell + 1}} \,{\dd z \over 2\pi\ic} \\[3mm]&=\pars{-1}^{n}\oint_{0\ <\ \verts{z}\ =\ a\ <\ 1} {1 \over z^{\ell + 1}\pars{1 + z}} \sum_{m = 0}^{n}{n \choose m}\pars{-z - 1}^{m}\,{\dd z \over 2\pi\ic} \\[3mm]&=\pars{-1}^{n}\oint_{0\ <\ \verts{z}\ =\ a\ <\ 1} {1 \over z^{\ell + 1}\pars{1 + z}} \bracks{1 + \pars{-z - 1}}^{n}\,{\dd z \over 2\pi\ic} \\[3mm]&=\oint_{0\ <\ \verts{z}\ =\ a\ <\ 1}{1 \over z^{\ell - n + 1}\pars{1 + z}} {\dd z \over 2\pi\ic} =\sum_{k = 0}^{\infty}\pars{-1}^{k}\oint_{0\ <\ \verts{z}\ =\ a\ <\ 1}{1 \over z^{\ell - n - k + 1}}{\dd z \over 2\pi\ic} \\[3mm]&=\sum_{k = 0}^{\infty}\pars{-1}^{k}\,\delta_{\ell - n,k} =\color{#66f}{\large\left\lbrace\begin{array}{lcl} \pars{-1}^{\ell - n} & \mbox{if} & \ell \geq n \\[2mm] 0&&\mbox{otherwise} \end{array}\right.} \end{align}

-
I applied your method to a combinatorial sum at this MSE link. –  Marko Riedel Aug 13 at 0:33