Evaluar suma de factorial para $ \sum ^{N+1} (último paso de una prueba por inducción)

Question

Estoy trabajando en el ejercicio 1.15 de Reconocimiento de Patrones y Aprendizaje Automático de Bishop, y me encontré con un paso que no entiendo. $$\sum^{D+1}_{i=1} \frac{(M + i - 2)!}{(M - 1)! (i - 1)!} = \frac{(D + M -1)!}{(D-1)!M!} + \frac{(D + M - 1)!}{D!(M - 1)!}$$ No estoy seguro de la forma correcta de evaluar la suma para $D+1$ y no conozco el truco o regla que produce los dos términos RHS.

Si alguien pudiera explicar cómo evaluar la suma, y la regla implícitamente utilizada aquí, ¡se lo agradecería!

Answer 1

Será más claro si utilizamos la notación binomial. El LHS es $$\sum_{i=1}^{D+1}\binom{M+i-2}{i-1}$$ Reindexación a partir de $0$ obtenemos $$\sum_{i=0}^D\binom{M-1+i}i$$ que es equivalente mediante la "identidad palo de hockey" a $\binom{M+D}D$ . El lado derecho es $\binom{M+D-1}{D-1}+\binom{M+D-1}D$ y puede reescribirse como $\binom{M+D}D$ a través de la identidad del triángulo de Pascal, estableciendo así la identidad original.

Answer 2

Escribiríamos:

$$\sum^{D+1}_{i=1} \frac{(M + i - 2)!}{(M - 1)! (i - 1)!} = \sum^{D}_{i=1} \frac{(M + i - 2)!}{(M - 1)! (i - 1)!} + \frac{(D + M - 1)!}{D!(M - 1)!}$$

Y luego utilizar la fórmula inductiva suministrada:

$$\sum^{D}_{i=1} \frac{(M + i - 2)!}{(M - 1)! (i - 1)! }= \frac{(D + M -1)!}{(D-1)!M!}=\binom{D+M-1}{D-1}$$

para llegar:

$$\sum^{D+1}_{i=1} \frac{(M + i - 2)!}{(M - 1)! (i - 1)!} = \frac{(D + M -1)!}{(D-1)!M!} + \frac{(D + M - 1)!}{D!(M - 1)!}$$

Podemos agrupar términos similares:

$$\frac{(D + M -1)!}{(D-1)!M!} + \frac{(D + M - 1)!}{D!(M - 1)!}= \frac{(D + M - 1)!}{D!M!}(D+M)$$

Y fíjate:

$$\frac{(D + M - 1)!}{D!M!}(D+M)=\frac{(D + M)!}{D!M!}$$

$$=\binom{D+M}{D}$$