# 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.

-

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$$

-
You might have pointed out that it's Vandemonde's identity, en.wikipedia.org/wiki/Vandermonde%27s_identity. Well, but there's something else interesting: it could be solved out by Zeilberger's algorithm, mathworld.wolfram.com/ZeilbergersAlgorithm.html – Frank Science Jun 12 '12 at 3:40

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*}

-