Prueba combinatoria de la caída del factorial y del teorema del binomio

Question

Para $n,m,k \in \mathbb{N}$ , demuestre la igualdad $$(n+m)^{\underline{k}}=\sum^{k}_{i=0}\binom ki \cdot n^{\underline{k-i}} \cdot m^{\underline{i}}$$ Aquí, $x^{\underline{j}}$ denota un factorial descendente, definido por $x^{\underline{j}} = \dfrac{x!}{\left(x-j\right)!} = x\left(x-1\right)\cdots\left(x-j+1\right)$ .

Puedo demostrar el teorema del binomio por sí mismo combinatoriamente y también la versión factorial descendente del mismo, pero combinado me doy contra un muro. ¿Alguna sugerencia?

Answer 1

¿De cuántas maneras se puede elegir $k$ bolas de un conjunto de $n$ diferentes bolas rojas y $m$ ¿bola verde diferente?

Respuesta

$$(n+m)^{\underline k}$$

Pero se pueden contar de otra manera. Primero supongamos que el $k$ las bolas son rojas, entonces $k-1$ son de color rojo y $1$ es verde, etc.

Esto da

$$\sum_{j=0}^k\binom kj n^{\underline j} m^{\underline {k-j}}$$

Answer 2

Prefiero el argumento combinatorio, pero es útil poder manipular las sumas y los factoriales descendentes, así que aquí está el paso de inducción de la prueba por inducción sobre $k$ .

$$\begin{align*} \sum_{i=0}^{k+1}\binom{k+1}in^{\underline{k+1-i}}m^{\underline i}&=\sum_{i=0}^{k+1}\left(\binom{k}i+\binom{k}{i-1}\right)n^{\underline{k+1-i}}m^{\underline i}\\ &=\sum_{i=0}^k\binom{k}in^{\underline{k+1-i}}m^{\underline i}+\sum_{i=0}^k\binom{k}in^{\underline{k-i}}m^{\underline{i+1}}\\ &=\sum_{i=0}^k\binom{k}i\left(n^{\underline{k+1-i}}m^{\underline i}+n^{\underline{k-i}}m^{\underline{i+1}}\right)\\ &=\sum_{i=0}^k\binom{k}in^{\underline{k-i}}m^{\underline i}\big((n-k+i)+(m-i)\big)\\ &=\sum_{i=0}^k\binom{k}in^{\underline{k-i}}m^{\underline i}(n-k+m)\\ &=(n+m-k)(n+m)^{\underline k}\\ &=(n+m)^{\underline{k+1}}\;. \end{align*}$$

Answer 3

Esto también se deduce de la identidad de Vandermonde, es decir $$\binom{n+m}{k}=\sum_{i=0}^k\binom{n}{i}\binom{m}{k-i}$$ que se puede demostrar utilizando un argumento similar al de los comités, a saber, dos formas de elegir un grupo de $k$ personas de $n$ hombres y $m$ mujeres. Multiplica ambos lados por $k!$ para conseguir que $$(n+m)^{\underline{k}} =\sum_{i=0}^k\binom{k}{i}n^{\underline i} m^{\underline {k-i}}$$ como se desee.