Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
up vote 5 down vote accepted

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

share|cite|improve this answer
You might have pointed out that it's Vandemonde's identity, Well, but there's something else interesting: it could be solved out by Zeilberger's algorithm, – 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


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

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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