# Recurrence relation for product of binomial coefficients

We all know the standard recurrence relation for binomial coefficients: $$\binom{n}{k-1} + \binom{n}{k} = \binom{n+1}{k}$$ Is there any finite-step recurrence relation one can write down for a product of binomials such as: $$f(n,k) = \binom{n}{k}\binom{m-n}{k}$$ where $m$ is a constant. A related question is: for gaussian distributions, the product of two gaussians is once again a gaussian. Is there such a relation for the product of binomial coefficients, possibly in terms of $\Gamma$ functions?

Thank you!

EDIT: Thanks for the hints! Unfortunately one key requirement is that the recurrence relation does not involve factors of $n$, $k$ or $m$ explicitly.

• Is $m$ to remain an absolute constant, or would you also be interested in a recursive way to compute $g(n,m,k)$ which would denote your $f(n,k)$ but with the $m$ thrown in as a third parameter? Jun 1, 2014 at 2:40
• Sure, if it makes it easier, we can let $m$ vary. Jun 1, 2014 at 2:51

There are a number of identities involving products of binomial coefficients or sums of products of binomial coefficients.

There's the (perhaps trivial)

$$\binom{n}{h}\binom{n-h}{k}=\binom{n}{k}\binom{n-k}{h}$$

One quite useful one is the Chu-Vandermonde identity

$${m+n \choose r}=\sum_{k=0}^r{m \choose k}{n \choose r-k}$$

for non-negative integer $m$,$n$ and $r$.

You can find a few additional results in the Wikipedia article on binomial coefficients.

I don't think these directly solve your problem though.

There is a "recursion" $f(n,0)=1$ and $$f(n,k+1)=\frac{(m-n-k)(n-k)}{(k+1)^2}\cdot f(n,k),$$ which can be shown using the factorial versions of the binomial coefficients. (If one doesn't like starting at $k=0$ can use $f(n,1)=(m-n)n$ to start out.)

$f(n,k)=\dfrac{n!(m-n)!}{k!(n-k)!(m-n-k)!(k)!}$

$f(n+1,k)=\dfrac{(n+1)!(m-n-1)!}{k!(n-k)!(m-n-k-1)!(k!)}$

From here $f(n+1,k)=\dfrac{f(n,k)(n+1)(m-n-k)}{(m-n)}$