Algebraic proof of a binomial sum identity. 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.
 A: 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$$
A: A straightforward proof by induction is possible, provided that you induct on the right thing, essentially $n+N$.
To simplify the notation, let $a=m-1$, $b=n+N-1$, and $c=n-1$; then the equation
$$\sum_{q=0}^N\binom{m + q - 1}{m-1}\binom{n + N - q - 1}{n-1} = \binom{m + n + N - 1}{N}$$
can (after applying symmetry to each binomial) be rewritten as
$$\sum_{k=0}^b\binom{a+k}a\binom{b-k}c=\binom{a+b+1}{a+c+1}\;.\tag{1}$$
I’ll show by induction on $b$ that for each $b\ge 0$, $(1)$ holds for all $a,c\ge 0$.
When $b=0$, both sides of $(1)$ are $1$ if $c=0$ and $0$ otherwise. Now assume that $(1)$ holds for some $b\ge 0$. Then
$$\begin{align*}
\sum_{k=0}^{b+1}\binom{a+k}a\binom{b+1-k}c&=\sum_{k=0}^{b+1}\binom{a+k}a\left(\binom{b-k}c+\binom{b-k}{c-1}\right)\\
&=\sum_{k=0}^b\binom{a+k}a\binom{b-k}c+\sum_{k=0}^b\binom{a+k}a\binom{b-k}{c-1}\\
&=\binom{a+b+1}{a+c+1}+\binom{a+b+1}{a+c}\\
&=\binom{a+b+2}{a+c+1}\;.
\end{align*}$$
