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?

  • $\begingroup$ There's a combinatorial proof for the formal power series. By writing $|x|\lt1$, you're making this about the convergence of actual power series, which is a whole different question and seems unlikely to be susceptible to combinatorial proofs. Would a combinatorial proof for the formal power series be good enough? $\endgroup$ – joriki Jul 18 '18 at 19:32
  • $\begingroup$ @joriki: That would be more than fantastic. I'll remove the convergent condition to make this much better as you suggested. $\endgroup$ – Bumblebee Jul 18 '18 at 19:34

$\binom{n+k-1}{k}$ is the number of ways to place $k$ indistinguishable 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*}


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


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.