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.


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


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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.