Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question
    
Does your summation begin from $m = l+1$? –  user17762 Apr 25 '11 at 17:55
1  
Then I assume you need to interpret $\binom{n}{r} = 0$ when $n < r$? –  user17762 Apr 25 '11 at 17:57
1  
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

3 Answers 3

up vote 5 down vote accepted

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

share|improve this answer
3  
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
1  
You are right, I forgot a term. Corrected. –  Plop Apr 25 '11 at 18:57

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

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

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.

share|improve this 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.) –  J. M. Apr 25 '11 at 18:56
    
I found a copy here –  user02138 Apr 25 '11 at 19:03
2  
@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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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