I came across this identity when working with energy partitions of Einstein solids. I have a combinatorial proof, but I'm wondering if there exists an algebraic proof.
$$\sum_{q=0}^N\binom{m + q – 1}{q}\binom{n + N – q – 1}{N – q} = \binom{m + n + N – 1}{N}$$
I've tried induction, but Pascal's Identity cannot simultaneously reduce the top and bottom argument for an inductive proof.
For those interested, a combinatorial proof of the identity can be given as follows: Consider the ways of distributing $N$ quanta of energy to a system of $n + m$ oscillators (where each oscillator can have any number of quanta). This is equivalent to the question of asking how many ways of putting $N$ objects into $n + m$ boxes. From the traditional stars and bars method, the total is given by
$$\binom{m + n + N – 1}{N}$$
which is the right-hand side. Alternatively, consider partitioning the units of energy between the first $m$ and the last $n$ oscillators. Give $q$ units of energy to the first $m$ oscillators. Then there remains $N – q$ units of energy for the latter $n$. Together, the number of states for this particular partition is
$$\binom{m + q – 1}{q}\binom{n + N – q – 1}{N – q}$$
Summing over all partitions gives the left-hand side.
Thanks for your time.
Best Answer
Let $$f_n(z)=\sum_{q=0}^\infty \binom {n+q-1}q z^q$$
Claim: This is $(1-z)^{-n}$.
Then $f_n(z)f_m(z) = f_{n+m}(z)$. But the left hand side of your formula is the coefficient of $z^N$ in $f_n(z)f_m(z)$, and the right hand side is the coefficient of $f_{n+m}(z)$.
The proof of the claim is the generalized binomial expansion, and uses the fact that $$\binom {-n} q = (-1)^q \binom {n+q-1}{q}$$
Alternatively, you can rewrite your statement as:
$$\sum_{q=0}^N \binom {-m} q \binom {-n}{N-q} = \binom {-(m+n)}q$$