# Summation of a factorial (total number terms in a polynomial)

By induction I can prove : $$\sum^{M}_{t=0}\frac{(t+D-1)!}{t!(D-1)!} = \frac{(D+M)!}{D!M!}$$

However, I couldn't derive the right hand side directly.

It would be of great help if anyone can solve it!!

-

$(1+x)^{M} (1+x)^{D} = (1+x)^{M+D}$

compute coefficient of $x^{D}$ on both sides.  on LHS, it is $$\sum^{M}_{t=0}\frac{(t+D-1)!}{t!(D-1)!}$$ and on it is RHS $$\frac{(D+M)!}{D!M!}$$

-

Here is a combinatorial proof.

Assume you have $D+1$ types of cakes, and you allowed to choose $M$ cakes. Of course you can take several cakes of the same type. The amount of possible choices is combination with repetitions: $${(D+1)+M - 1 \choose D}=\frac{(M+D)!}{M!D!}\tag{1}$$ How can we classify all possible choices? We say our choice belongs to the $t$-th class if we choose $M-t$ cakes of the first type. How many choices of $t$-th type are there? Well this is amount of possible choices of remaining $t$ cakes from remaining $D$ types of cakes, which is equal to $${D+t-1 \choose D-1}=\frac{(D+t-1)!}{(D-1)!t!}$$ Since we are allowed to take only $M$ cakes, there are $M+1$ classes - $t$ varies from $0$ to $M$. Now we see that total amount of choices is sum of amount of choices over all classes: $$\sum\limits_{t=0}^M{D+t-1\choose D-1}=\sum\limits_{t=0}^M\frac{(D+t-1)!}{(D-1)!t!}$$ On the other hand this amount is equals to $(1)$.

-

Start with the binomial coefficient relation $${n\choose D}={n-1\choose D}+{n-1\choose D-1}$$ rewritten as $${n\choose D}-{n-1\choose D}={n-1\choose D-1}.$$

Adding these increments gives $${D+M\choose D}-{D-1\choose D}=\sum_{n=D}^{D+M}{n-1\choose D-1}.$$ Since ${D-1\choose D}=0$ this gives you the sum that you want.

Here's another combinatorial argument to complement Norbert's. The number of ways to select $D$ distinct values from the set $\{1,2,\dots,D+M\}$ is $${D+M\choose D}.$$ For $0\leq t\leq M$, the number of such selections with maximum value $D+t$ is
$${D-1+t\choose D-1}.$$