Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I have run across the following multinomial series: $$ \sum_{j = a}^{N} \binom{N}{j} \binom{j}{a} d^{-j} $$ Here, $d>1$. This seems like a formula which has either a well-known identity, or which has no further closed form or simplification. Can anyone shed any light on this formula, or possibly point me to a standard reference?

share|improve this question
for $a=0$ we have $(1+1/d)^N$ (not that this helps)... –  yoyo Mar 3 '11 at 20:31
add comment

4 Answers

up vote 7 down vote accepted

$$\sum_{j = a}^{N} \binom{N}{j} \binom{j}{a} d^{-j} = \sum_{j = a}^{N} \binom{N}{a} \binom{N-a}{j-a} d^{-j} = \binom{N}{a} \sum_{j = 0}^{N-a} \binom{N-a}{j} d^{-j-a} $$ $$= d^{-a} \binom{N}{a} \sum_{j = 0}^{N-a} \binom{N-a}{j} d^{-j} = d^{-a} \binom{N}{a} (1+d^{-1})^{N-a}.$$ The first step uses what's called trinomial revision. See, for example, Concrete Mathematics, p. 174. The last step uses the binomial theorem.

share|improve this answer
add comment

You can use $${N \choose j}{j \choose a} = \frac{ N!}{j! (N-j)!} \frac{j!}{a! (j-a)!} =\frac{N!}{a!(N-a)!} \frac{(N-a)!}{(j-a)! (N-j)!} = {N \choose a}{ N-a \choose j-a}$$ to write your expression as $${N \choose a} \sum_{j=a}^N { N-a \choose j-a} d^{-j}= {N \choose a} d^{-a} \sum_{j=0}^{N-a} { N -a \choose j} d^{-j} = {N \choose a} d^{-a} (1+1/d)^{N-a}.$$ (using binomial series)

share|improve this answer
add comment

Since you mentioned the word "multinomial", here is another way, using the Multinomial theorem.


$$(1 + x/d + x)^n = \sum_{p+q+r=n} {n \choose p,q,r} 1^p \cdot (x/d)^q \cdot x^r$$

$$= \sum_{a=0}^{n} \sum_{j=a}^{n} {n \choose a,j-a,n-j} 1^{a} \cdot (x/d)^{j-a} \cdot x^{n-j}$$

$$ = \sum_{a=0}^{n} \left(\sum_{j=a}^{n} {n \choose j} {j \choose a} d^{a-j}\right) x^{n-a}$$

Expand $\displaystyle (1 + x(1+1/d))^n$ using binomial theorem and equate the coefficient of $\displaystyle x^{n-a}$ on both sides to get

$$ {n \choose a} (1 + 1/d)^{n-a} = \sum_{j=a}^{n} {n \choose j} {j \choose a} d^{a-j}$$

and so

$$ {n \choose a} d^{-a} (1 + 1/d)^{n-a} = \sum_{j=a}^{n} {n \choose j} {j \choose a} d^{-j}$$

Here are a couple more answers which use similar ideas:

Beautiful identity: $\sum_{k=m}^n (-1)^{k-m} \binom{k}{m} \binom{n}{k} = \delta_{mn}$

Non-probabilistic proofs of a binomial coefficient identity from a probability question

share|improve this answer
add comment

Answer: $$\binom{N}{a} d^{-a}(1+d^{-1})^{N-a} \; .$$

I'll leave it up to you to check it.

share|improve this answer
add comment

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.