A combinatorial identity: $\sum _{i + j = k} (-1)^i {n \choose i} {n + j - 1 \choose n - 1 } = 0 $

Question

I proved this combinatorial identity while doing some linear algebra.

For any positive integer $k$, $$ \sum _{i + j = k} (-1)^i {n \choose i} {n + j - 1 \choose n - 1 } = 0 $$

I was wondering what could be other ways of proving this.

EDIT: I thought I should mention how this identity comes up in linear algebra. For a vector space $V$ of dimension $n$, let $\Lambda(V)$ denote the exterior algebra and $ S(V) $ denote the symmetric algebra. There is a long exact sequence of vector spaces with $k + 1$ terms whose $i^{th}$ term is $$\Lambda ^ {i-1}(V) \otimes S^{k - i +1}(V)$$ One can then find the Euler characteristic of this exact sequence to get the above identity. It a question in one of the exercises in the book by Brocker-Tom Dieck on Lie groups.

Answer 1

One can give a purely combinatorial argument. First rewrite the summation as

$$\sum_{i=0}^k(-1)^i\binom{n}i\binom{n+k-i-1}{n-1}\;.\tag{1}$$

Suppose that we have $k$ indistiguishable balls to be distributed amongst $n$ distinguishable boxes. Let $S$ be fixed set of the $n$ boxes, and let $i=|S|$. We can put one ball into each box in $S$ and then distribute the remaining $k-i$ balls in $\binom{n+k-i-1}{n-1}$ ways, so $\binom{n+k-i-1}{n-1}$ is the number of ways of distributing the $k$ balls so that each box in $S$ is non-empty. By a straightforward inclusion-exclusion argument $(1)$ is the number of ways to distribute the $k$ balls so that every box is empty, which is clearly $0$ for all $k\ge 1$.

Answer 2

The power series approach using:

$$(1-z)^{-n} =\sum_{i=0}^\infty \binom{n+i-1}{n-1}z^i$$

[You can prove this by induction on $n$, using repeated differentiation, or other methods.]

Multiply by the polynomial $(1-z)^n$, and note that, when $k>0$, the coefficient of the $z^k$ should be $0$ in the result.

Answer 3

$\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{\dsc}[1]{\displaystyle{\color{red}{#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{\Li}[1]{\,{\rm Li}_{#1}} \newcommand{\norm}[1]{\left\vert\left\vert\, #1\,\right\vert\right\vert} \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{\ul}[1]{\underline{#1}} \newcommand{\verts}[1]{\left\vert\, #1 \,\right\vert}$ $\ds{\sum _{i\ +\ j\ =\ k}\pars{-1}^{i}{n \choose i}{n + j - 1 \choose n - 1} = 0:\ {\large ?}}$.

---

\begin{align}&\color{#66f}{\large% \sum _{i\ +\ j\ =\ k}\pars{-1}^{i}{n \choose i}{n + j - 1 \choose n - 1}} \\[5mm]&=\sum _{j\ =\ 0}^{\infty}\ \sum _{m\ =\ 0}^{\infty} \pars{-1}^{m}{n \choose m}{n + j - 1 \choose j}\ \overbrace{% \oint_{\verts{z}\ =\ 1^{-}}\,\,\,\, {1 \over z^{-m - j + k + 1}}\,\,{\dd z \over 2\pi\ic}} ^{\dsc{\delta_{m\ +\ j,k}}} \\[5mm]&=\oint_{\verts{z}\ =\ 1^{-}}\,\,\,\,{1 \over z^{k + 1}}\ \overbrace{\bracks{\sum _{m\ =\ 0}^{\infty}{n \choose m}\pars{-z}^{m}}} ^{\dsc{\pars{1 - z}^{n}}}\ \overbrace{% \bracks{\sum _{j\ =\ 0}^{\infty}{-n \choose j}\pars{-z}^{\,j}}} ^{\dsc{\pars{1 - z}^{-n}}}\ \,{\dd z \over 2\pi\ic} \\[5mm]&=\oint_{\verts{z}\ =\ 1^{-}}\,\,\,\,{1 \over z^{k + 1}} \,{\dd z \over 2\pi\ic} =\color{#66f}{\large\left\{\begin{array}{lcrcl} 0 & \color{#000}{\mbox{if}} & k & \not= & 0 \\[1mm] 1 & \color{#000}{\mbox{if}} & k & = & 0 \end{array}\right.} \end{align}