Prueba algebraica de que$\binom{n+k-1}{k} = \sum\limits_{i=0}^k \binom{(n-1)+(k-i)-1}{k-i}$

Question

Demostrar (algebraicamente) que $$f_k(n) = \binom{n+k-1}{k} = \sum\limits_{i=0}^k \binom{(n-1)+(k-i)-1}{k-i} = \sum\limits_{i=0}^k f_{k-i}(n-1)$$ for $n \geq 2$ and that $f_k(1) = 1$ for all $k$.

A continuación, muestran que si $$f_k(n) = \sum\limits_{i=0}^k f_{k-i}(n-1)$$ for $n\geq 2$ and $f_k(1) = 1$ for all $k$, then $f_k(n) = \binom{n+k-1}{k}$.

---

El intento de la primera: es fácil ver que $f_k(1) = 1$ para todos los $k$ por sustitución. Yo no estoy tan seguro acerca de qué, así que con la suma de los coeficientes binomiales. Estoy seguro de que hay una manera de utilizar la $ \sum\limits_{i=0}^k \binom{k}{i}x^i = (x+1)^k$, ya sea directamente o en un doble de la suma, pero no estoy seguro de cómo manipular el sumando en un formulario.

Para el segundo: después de la primera se resuelve, es trivial, ya que de acuerdo a $n=1$ y si están de acuerdo para $n = N-1$, deben estar de acuerdo para $n=N$ por la identidad de la primera. Así que la principal dificultad de este problema viene de la primera parte.

---

Edit: también debo señalar que yo puedo entender la identidad relativa $f_k(n)$ con el número de maneras de elegir un orden de $n$-tupla de números de la adición de a $k$, o, equivalentemente, el número de $k$-grado de términos en una $n$-dimensiones polinomio. Sin embargo, mis intentos de conversión que la intuición en una prueba algebraica no ha ido a ninguna parte.

Answer 1

Tenemos $$ \eqalign{ & \sum\limits_{0\, \le \,i\, \le \,k} {\left( \matriz{ n - 2 + k - i \cr k - i \cr} \right)} = \cr & = \sum\limits_{0\, \le \,j\, \le \,k} {\left( \matriz{ n - 2 + j \cr j \cr} \right)} = \quad \quad (1) \cr & = \sum\limits_{\left( {0\, \le } \right)\,j\,\left( { \le \,k} \right)} {\left( \matriz{ k - j \cr k - j \cr} \right)\left( \matriz{ n - 2 + j \cr j \cr} \right)} = \quad \quad (2) \cr & = \sum\limits_{\left( {0\, \le } \right)\,j\,\left( { \le \,k} \right)} {\left( { - 1} \right)^{\,k - j} \left( \matriz{ - 1 \cr k - j \cr} \right)\left( { - 1} \right)^{\,j} \left( \matriz{ - n + 1 \cr j \cr} \right)} = \quad \quad (3)\cr & = \left( { - 1} \right)^{\,k} \sum\limits_{\left( {0\, \le } \right)\,j\,\left( { \le \,k} \right)} {\left( \matriz{ - 1 \cr k - j \cr} \right)\left( \matriz{ - n + 1 \cr j \cr} \right)} = \quad \quad (4) \cr & = \left( { - 1} \right)^{\,k} \left( \matriz{ - n \cr k \cr} \right) = \quad \quad (5) \cr & = \left( \matriz{ n + k - 1 \cr k \cr} \right) \quad \quad (6) \cr} $$ donde:
(1) cambio de índice
(2) la sustitución de la suma de los límites con el binomio
(3) superior negación
(5) de convolución (6) superior negación

Nota (2):

El binomio $\binom{k-j}{k-j}$ es igual a $1$ para $j \le k$ y es nulo para $k<j$.
Por lo tanto se puede utilizar para reemplazar el límite superior para $j$ en la suma.
Por otro lado, el segundo binomio intrínsecamente asegura el límite inferior $0 \le j$.
Por lo tanto, podemos dejar el índice de libertad de tomar todos los valores: es por eso que indica el límite entre paréntesis.
Eso es un "truco" en el tiempo de muchos útiles en la manipulación de la binomial sumas, y estoy en deuda con el famoso "Concreto de las Matemáticas para la enseñanza.

Answer 2

Deje que $[x^j]:f(x)$ denote el coeficiente de $x^j$ de la función $f(x)$ . Tenemos \begin{eqnarray*} \sum_{i=0}^{k} \binom{n+k-i-2}{k-i} &=& \sum_{i=0}^{k} [x^{k-i}]: (1+x)^{n+k-i-2} \\ &=& [x^k]: \sum_{i=0}^{k} (1+x)^{n+k-2} \left(\frac{x}{x+1} \right)^i \\ &=& [x^k]: (1+x)^{n+k-2} \sum_{i=0}^{\infty} \left(\frac{x}{x+1} \right)^i \\ &=& [x^k]: (1+x)^{n+k-1} = \binom{n+k-1}{k}. \end {eqnarray *}