I'm working on exercise 1.15 from Bishop's Pattern Recognition and Machine Learning, and ran into a step I don't understand. $$\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)!}$$ I'm not sure of the proper way to evaluate the sum for $D+1$ and don't know the trick or rule that produces the two RHS terms.
If anyone could explain how to evaluate the sum, and the rule implicitly used here, I would appreciate it!
On
It will be clearer if we use binomial notation. The LHS is $$\sum_{i=1}^{D+1}\binom{M+i-2}{i-1}$$ Reindexing to start from $0$, we get $$\sum_{i=0}^D\binom{M-1+i}i$$ which is equivalent via the "hockey-stick identity" to $\binom{M+D}D$. The RHS is $\binom{M+D-1}{D-1}+\binom{M+D-1}D$ and can be rewritten as $\binom{M+D}D$ via the Pascal's triangle identity, thus establishing the original identity.
We would write:
$$\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)!}$$
And then use the supplied inductive formula:
$$\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}$$
to arrive at:
$$\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)!}$$
We can group like terms:
$$\frac{(D + M -1)!}{(D-1)!M!} + \frac{(D + M - 1)!}{D!(M - 1)!}= \frac{(D + M - 1)!}{D!M!}(D+M)$$
And notice:
$$\frac{(D + M - 1)!}{D!M!}(D+M)=\frac{(D + M)!}{D!M!}$$
$$=\binom{D+M}{D}$$