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

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

3 Answers 3

Reset to default
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.

$\endgroup$
3
  • $\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. ain't a mathematician
    Apr 25, 2011 at 18:56
  • $\begingroup$ I found a copy here $\endgroup$
    – user02138
    Apr 25, 2011 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, 2011 at 19:59
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.

$\endgroup$
2
  • 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, 2011 at 18:38
  • 1
    $\begingroup$ You are right, I forgot a term. Corrected. $\endgroup$
    – Plop
    Apr 25, 2011 at 18:57
1
$\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}

$\endgroup$
1
  • $\begingroup$ I applied your method to a combinatorial sum at this MSE link. $\endgroup$
    – Marko Riedel
    Aug 13, 2014 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.