6
$\begingroup$

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?

$\endgroup$
1
  • $\begingroup$ for $a=0$ we have $(1+1/d)^N$ (not that this helps)... $\endgroup$
    – yoyo
    Mar 3, 2011 at 20:31

5 Answers 5

7
$\begingroup$

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

$\endgroup$
4
$\begingroup$

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)

$\endgroup$
4
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

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

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Sorry. I didn't see your answer before I wrote my answer. Thanks. $\endgroup$ Aug 21, 2014 at 22:11

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .