6
$\begingroup$

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!

|cite|improve this question
$\endgroup$
  • $\begingroup$ Does your summation begin from $m = l+1$? $\endgroup$ – user17762 Apr 25 '11 at 17:55
  • 1
    $\begingroup$ Then I assume you need to interpret $\binom{n}{r} = 0$ when $n < r$? $\endgroup$ – user17762 Apr 25 '11 at 17:57
  • 1
    $\begingroup$ Perhaps you could mention how it arose? $\endgroup$ – davidlowryduda♦ Apr 25 '11 at 17:57
  • $\begingroup$ No, the sum must start at $m = 0$. I interpret $\binom{-1}{l} = (-1)^{l}$. $\endgroup$ – user02138 Apr 25 '11 at 18:01
  • $\begingroup$ @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$.)? $\endgroup$ – Aryabhata Apr 25 '11 at 18:29
6
$\begingroup$

$$\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.

|cite|improve this answer
$\endgroup$
  • 3
    $\begingroup$ 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$... $\endgroup$ – Fabian Apr 25 '11 at 18:38
  • 1
    $\begingroup$ You are right, I forgot a term. Corrected. $\endgroup$ – Plop Apr 25 '11 at 18:57
8
$\begingroup$

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.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ 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.) $\endgroup$ – J. M. is a poor mathematician Apr 25 '11 at 18:56
  • $\begingroup$ I found a copy here $\endgroup$ – user02138 Apr 25 '11 at 19:03
  • 2
    $\begingroup$ @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." $\endgroup$ – Mike Spivey Apr 25 '11 at 19:59
2
$\begingroup$

$\newcommand{\angles}[1]{\left\langle\, #1 \,\right\rangle} \newcommand{\braces}[1]{\left\lbrace\, #1 \,\right\rbrace} \newcommand{\bracks}[1]{\left\lbrack\, #1 \,\right\rbrack} \newcommand{\ceil}[1]{\,\left\lceil\, #1 \,\right\rceil\,} \newcommand{\dd}{{\rm d}} \newcommand{\ds}[1]{\displaystyle{#1}} \newcommand{\expo}[1]{\,{\rm e}^{#1}\,} \newcommand{\fermi}{\,{\rm f}} \newcommand{\floor}[1]{\,\left\lfloor #1 \right\rfloor\,} \newcommand{\half}{{1 \over 2}} \newcommand{\ic}{{\rm i}} \newcommand{\iff}{\Longleftrightarrow} \newcommand{\imp}{\Longrightarrow} \newcommand{\pars}[1]{\left(\, #1 \,\right)} \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}} \newcommand{\pp}{{\cal P}} \newcommand{\root}[2][]{\,\sqrt[#1]{\vphantom{\large A}\,#2\,}\,} \newcommand{\sech}{\,{\rm sech}} \newcommand{\sgn}{\,{\rm sgn}} \newcommand{\totald}[3][]{\frac{{\rm d}^{#1} #2}{{\rm d} #3^{#1}}} \newcommand{\verts}[1]{\left\vert\, #1 \,\right\vert}$ $\ds{\sum_{m = 0}^{n}\pars{-1}^{n - m}{n \choose m}{m - 1 \choose \ell}:\ {\large ?}.\qquad\ell \geq 0}$

\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}

|cite|improve this answer
$\endgroup$
  • $\begingroup$ I applied your method to a combinatorial sum at this MSE link. $\endgroup$ – Marko Riedel Aug 13 '14 at 0:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.