# Identity for $\sum\limits_{j = a}^{N} \binom{N}{j} \binom{j}{a} d^{-j}$?

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?

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

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

-
Sorry. I didn't see your answer before I wrote my answer. Thanks. – Felix Marin Aug 21 '14 at 22:11