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?

  • 0
    for $a=0$ we have $(1+1/d)^N$ (not that this helps)...2011-03-03

5 Answers 5

7

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

4

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)

4

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

1

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

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

0

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.

  • 0
    Sorry. I didn't see your answer before I wrote my answer. Thanks.2014-08-21