Demostrando $\sum_{m=0}^M \binom{m+k}{k} = \binom{k+M+1}{k+1}$

Question

Demostrar que $$\sum_{m=0}^M \binom{m+k}{k} = \binom{k+M+1}{k+1}$$ by computing the coefficient of $z^M$ in the identity $$(1 + z + z^2 + \cdots ) \cdot \frac{1}{(1-z)^{k+1}} = \frac1{(1-z)^{k+2}}.$$

Reconozco que la identidad que se dan a partir de la generación de funciones, pero, ¿cómo ayudar a probar la identidad?

Alguien puede proporcionar una sugerencia en cuanto a cómo abordar este problema?

Answer 1

En esta respuesta, puedo probar la identidad $$ \binom {n}{k}=(-1)^k\binom{n+k-1}{k}\etiqueta{1} $$ Aquí es una generalización de la identidad en cuestión, demostrado el uso de la Identidad de Vandermonde $$ \begin{align} \sum_{m=0}^M\binom{m+k}{k}\binom{M-m}{n} &=\sum_{m=0}^M\binom{m+k}{m}\binom{M-m}{M-m-n}\tag{2}\\ &=\sum_{m=0}^M(-1)^m\binom{-k-1}{m}(-1)^{M-m-n}\binom{-n-1}{M-m-n}\tag{3}\\ &=(-1)^{M-n}\sum_{m=0}^M\binom{-k-1}{m}\binom{-n-1}{M-m-n}\tag{4}\\ &=(-1)^{M-n}\binom{-k-n-2}{M-n}\tag{5}\\ &=\binom{M+k+1}{M-n}\tag{6}\\ &=\binom{M+k+1}{n+k+1}\tag{7} \end{align} $$ Explicación:
$(2)$: $\binom{n}{k}=\binom{n}{n-k}$
$(3)$: aplicar $(1)$ a cada coeficiente binomial
$(4)$: combinar los poderes de $-1$, el cual puede luego ser tirado al frente
$(5)$: aplicar Vandermonde
$(6)$: aplicar $(1)$
$(7)$: $\binom{n}{k}=\binom{n}{n-k}$

Para obtener la identidad de la cuestión, establezca $n=0$.

Answer 2

Recordar que: $$ (1+x)^m = \sum_k \binom{m}{k} x^k $$ Por lo que la suma $$ \sum_{m=0}^M \binom{m+k}{k} $$ es el coeficiente de $ x^k $ en la: $$ \sum_{m=0}^M (1+x)^{m+k} $$ Sí? Así que ahora uso la serie geométrica de la fórmula dada: $$ \sum_{m=0}^M (1+x)^{m+k} = -\frac{(1+x)^k}{x} \left( 1 - (1+x)^{M+1} \right) $$ Y ahora usted quiere saber lo que es el coeficiente de $x^k $ en allí. Tienes de aquí.

Answer 3

Una técnica estándar para probar estas identidades $\sum_{i=0}^Mf(i)=F(M)$, que implica por un lado una suma donde sólo el límite superior $M$ es variable y en la otra mano una expresión explícita en términos de$~M$, es el uso de la inducción en$~M$. Esto equivale a mostrar que la $f(M)=F(M)-F(M-1)$ (y eso $F(0)=f(0)$). Esto es similar a utilizar el teorema fundamental del cálculo en demostrar que las $\int_0^{x_0}f(x)\mathrm dx=F(x_0)$ mediante el establecimiento $f(x)=F'(x)$ (e $F(0)=0$).

Así que aquí usted necesita para comprobar (aparte de la evidente a partir de casos $M=0$$\binom{M+k}k=\binom{M+k+1}{k+1}-\binom{M+k}{k+1}$. Esto es sólo en la instancia de Pascal de la recurrencia de los coeficientes binomiales.

Answer 4

Recuerda que, por $k\in\Bbb N$ tenemos la generación de la función

$$\sum_{n\ge 0}\binom{n+k}kx^n=\frac1{(1-x)^{k+1}}\;.$$

La identidad en la pregunta por lo tanto se puede escribir como

$$\left(\sum_{n\ge 0}\binom{n+k}kx^n\right)\left(\sum_{n\ge 0}x^n\right)=\sum_{n\ge 0}\binom{n+k+1}{k+1}x^n\;.$$

El coeficiente de $x^n$ en el producto de la izquierda es

$$\sum_{i=0}^n\binom{i+k}k\cdot1=\sum_{i=0}^n\binom{i+k}k\;,$$

y el $n$-ésimo término de la discreta convolución de las secuencias de $\left\langle\binom{n+k}k:n\in\Bbb N\right\rangle$$\langle 1,1,1,\dots\rangle$. Y en este punto en el que está prácticamente hecho.