Combinatorial proof of Negative Binomial Identity $(1+x)^{-n}= \sum_{k=0}^{\infty} (-1)^k \binom{n+k-1}{k} x^k$

Question

For the (usual) Binomial theorem with positive integer exponent, there is a well known nice combinatorial proof.

I am eager to learna similar argument for the proof of negative binomial series: $$(1+x)^{-n}= \sum_{k=0}^{\infty} (-1)^k \binom{n+k-1}{k} x^k.$$

I found that the quantity $\binom{n+k-1}{k}$ has the combinatorial interpretation that "the number of ways to distributing $k$ indistinguishable balls into $n$ distinguishable boxes without any restriction."

I tried to use that fact, but could not find the right trick. Do any of you know a way to go through this?

Answer 1

$\binom{n+k-1}{k}$ is the number of ways to place $k$ indistinguishable balls into $n$ boxes. Consider $k$ stars \begin{eqnarray*} \underbrace{** \cdots *}_{ k \text{ stars}} \end{eqnarray*} insert $n-1$ bars to form $n$ boxes \begin{eqnarray*} \underbrace{** }_{ k_1 \text{ stars}} \mid \underbrace{*** }_{ k_2 \text{ stars}} \mid \cdots \mid \underbrace{*}_{ k_n \text{ stars}} \\ \sum_{i=1}^{n} k_i=k. \end{eqnarray*} This is the same as picking the terms from \begin{eqnarray*} (1+x+\cdots+x^{k_1}+\cdots) (1+x+\cdots+x^{k_2}+\cdots) \cdots (1+x+\cdots+x^{k_n}+\cdots) \end{eqnarray*} So \begin{eqnarray*} \frac{1}{(1-x)^n} =\sum_{k=0}^{\infty} \binom{n+k-1}{k} x^k . \end{eqnarray*}

Answer 2

Here is the same solution, but painfully obfuscated by childishly refusing to just make the $x \mapsto -x$ substitution and call it a day.

Interpret the left hand side as $$(1+x)^{-n} = (1 - x+x^2 - x^3 + \cdots)^n$$ When expanding this product out, we choose one monomial $x^j$ from each of the $n$ factors; if $j$ is even, this comes with a $+$ sign, and if $j$ is odd, this comes with a $-$ sign. Thus, the coefficient of $x^{k}$ in the expanded product is the number of ways to write $k$ as a sum of $n$ nonnegative integers, where each way is weighted by $(-1)^{\text{number of odd integers in our way}}$. More precisely, the coefficient of $x^k$ is $$\sum_{a_1 + a_2 + \cdots + a_{n} = k, a_i \ge 0} (-1)^{\text{number of } a_i's \text{ that are odd}}$$ But this is precisely $$\#\{n-\text{tuples with even number of odds}\}-\#\{n-\text{tuples with odd number of odds}\}$$ Finally, note that $k$ is even iff there are an even number of odds among the $a_i$'s. Thus, the number is just $$(-1)^k \#\{n-\text{tuples adding to } k\} = (-1)^k \binom{n+k-1}{k}$$