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

5 Answers 5

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

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

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

Expand

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

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

Suppose we seek to evaluate $$\sum_{j=a}^N {N\choose j}{j\choose a} d^{-j}.$$

Start from $${j\choose a} = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{a+1}} (1+z)^j \; dz.$$

Note that with $j$ and $a$ integers when $j\lt a$ then $j-a \lt 0$ and $j-(a+1) \lt -1$ so we may extend the sum to start at $j=0$ because the extra contribution is zero.

This gives for the sum the integral $$\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{a+1}} \sum_{j=0}^N {n\choose j} \times (1+z)^j \times d^{-j} \; dz.$$

This simplifies to $$\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{a+1}} \left(\frac{1+z}{d}+1\right)^N \; dz$$ which is $$\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{a+1}} \left(\frac{1+d+z}{d}\right)^N \; dz.$$

Hence the closed form is $$[z^a] \left(\frac{1+d+z}{d}\right)^N = \frac{1}{d^N} [z^a] (1+d+z)^N = \frac{1}{d^N} {N\choose a} (1+d)^{N-a}$$

This finally yields $$\frac{1}{d^a} \frac{1}{d^{N-a}} {N\choose a} (1+d)^{N-a} = \frac{1}{d^a} {N\choose a} \left(1 + \frac{1}{d}\right)^{N-a}.$$

A trace as to when this method appeared on MSE and by whom starts at this MSE link.

share|improve this answer
    
Sorry. I didn't see your answer before I wrote my answer. Thanks. –  Felix Marin Aug 21 at 22:11

Your Answer

 
discard

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.