prueba alternativa a la inducción, identidad del binomio suma

Question

$\displaystyle \sum_{q=0}^{k} \begin{pmatrix}n-1+q\\ n-1 \end{pmatrix} = \begin{pmatrix}n+k\\n \end{pmatrix} $

inducción

$\begin{pmatrix}n \\ k \end{pmatrix} := \frac{n!}{(n-k)!k!}$

Principio de inducción: $k=0 \rightarrow \begin{pmatrix} n-1 \\ n-1 \end{pmatrix} = \begin{pmatrix} n \\ n \end{pmatrix} = 1 $

Paso de inducción: $k\rightarrow k+1: \sum_{q=0}^{k+1} \begin{pmatrix} n-1+q\\n-1 \end{pmatrix} = (\sum_{q=0}^{k} \begin{pmatrix} n-1+q\\n-1 \end{pmatrix}) + \pmatrix{n-1+k+1\\n-1} $

$\displaystyle = \begin{pmatrix}n+k \\ n \end{pmatrix} + \begin{pmatrix} n+k \\ n-1 \end{pmatrix} = \frac{(n+k)!}{k!(n)!}+ \frac{(n+k)!}{(k+1)!(n-1)!} =$

$\displaystyle =\frac{(n+k)!(k!n!+(k+1)k!(n-1)!}{k!n!(k+1)!(n-1)!} = \frac{(n+k)!(n+k+1)}{n!(k+1)!} = \begin{pmatrix}n+k+1 \\ n \end{pmatrix}$

---

¿Conoces otra manera de mostrar esto? Por favor Dile.

Answer 1

$\binom{n+k}{n}$ es el número de maneras de elegir a $n$ objetos de $n+k$ posibilidades.

Con el fin de seleccionar $n$ objetos de $n+k$ posibilidades, también podemos proceder como sigue: número de los objetos de $1$ través $n+k$. En primer lugar, elegir el objeto con el número más grande que se seleccione, debe ser numerada en algún lugar entre el $n$ $n+k$ (de lo contrario, usted no puede captar $n$ total de objetos); dicen que es numerado $n+q$,$q\in\{0,\ldots,k\}$. A continuación, usted todavía tiene que recoger $n-1$ objetos de la primera $n+q-1$ objetos; esto puede hacerse precisamente en $\binom{n+q-1}{n-1}$ maneras.

Puesto que usted puede hacer esto para cada valor de $q\in\{0,\ldots,k\}$, la suma de estas posibilidades, el resultado será una selección de $n$ objetos de $n+k$ posibilidades; es decir, $$\sum_{q=0}^{k}\binom{n+q-1}{n-1} = \binom{n+k}{n}.$$

Answer 2

Otra forma es utilizar el aceite de la serpiente:

$\begin{align} \sum_{n \ge 1} z^n \sum_{0 \le q \le k} \binom{n + q - 1}{n - 1} &= \sum_{0 \le q \le k} z^{1 - q} \sum_{n \ge 1} \binom{n + q - 1}{q} z^{n + q - 1} \\ &= \sum_{0 \le q \le k} z^{1 - q} \sum_{s \le 0} \binom{s}{q} z^s \\ &= \sum_{0 \le q \le k} z^{1 - q} \frac{z^q}{(1 - z)^{q + 1}} \\ &= \frac{z}{1 - z} \sum_{0 \le q \le k} (1 - z)^{-q} \\ &= \frac{z}{1 - z} \frac{1 - (1 - z)^{-k - 1}}{1 - (1 - z)^{-1}} \\ &= \frac{1}{(1 - z)^{k + 1}} - 1 \end {Alinee el} $

Ahora queremos que el coeficiente de $z^n$:

$\begin{align} [z^n] \frac{1}{(1 - z)^{k + 1}} &= (-1)^n \binom{-k - 1}{n} \\ &= \binom{n + k + 1 - 1}{k + 1 - 1} \\ &= \binom{n + k}{k} \\ &= \binom{n + k}{n} \end {Alinee el} $