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?
Identity for $\sum\limits_{j = a}^{N} \binom{N}{j} \binom{j}{a} d^{-j}$?
-
0for $a=0$ we have $(1+1/d)^N$ (not that this helps)... – 2011-03-03
5 Answers
$\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.
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)
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
Answer: $\binom{N}{a} d^{-a}(1+d^{-1})^{N-a} \; .$
I'll leave it up to you to check it.
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.
-
0Sorry. I didn't see your answer before I wrote my answer. Thanks. – 2014-08-21