Prueba combinatoria de identidad Binomial Negativa

Question

Para el (como es habitual) teorema del Binomio con exponente entero positivo, es conocida agradable combinatoria prueba.

Estoy con ganas de learna argumento similar para la prueba de la binomial negativa de la serie: $$(1+x)^{-n}= \sum_{k=0}^{\infty} (-1)^k \binom{n+k-1}{k} x^k.$$

He encontrado que la cantidad de $\binom{n+k-1}{k}$ tiene la combinatoria interpretación de que "el número de maneras de distribuir $k$ indistinguibles de las pelotas en $n$ distinguibles cajas sin ningún tipo de restricción".

Traté de usar ese hecho, pero no podía encontrar el truco. ¿Alguno de ustedes sabe de una manera de ir a través de esto?

Answer 1

$\binom{n+k-1}{k}$ es el número de maneras de colocar $k$ indistinguibles en $n$ cajas. Considerar $k$-estrellas\begin{eqnarray*} \underbrace{ \cdots }_{ k \text{ stars}} \end{eqnarray } insertar $n-1$barras de % a $n$ casillas de formularios\begin{eqnarray*} \underbrace{* }_{ k_1 \text{ stars}} \mid \underbrace{ }_{ k2 \text{ stars}} \mid \cdots \mid \underbrace{*}{ kn \text{ stars}} \ \sum{i=1}^{n} k_i=k. \end{eqnarray } es lo mismo como escoger los términos de\begin{eqnarray} (1+x+\cdots+x^{k_1}+\cdots) (1+x+\cdots+x^{k_2}+\cdots) \cdots (1+x+\cdots+x^{kn}+\cdots) \end, {eqnarray } lo\begin{eqnarray} \frac{1}{(1-x)^n} =\sum{k=0}^{\infty} \binom{n+k-1}{k} x^k . \end{eqnarray *}

Answer 2

Aquí le damos la misma solución, pero dolorosamente alterada por infantilmente negarse a hacer la sustitución de $x \mapsto -x$ y llamar un día.

Interpretar el lado izquierdo como $$(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 {número de impares enteros en nuestro camino}} $. More precisely, the coefficient of $x ^ k $ is $$\sum_{a_1 + a2 + \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}$