Binomial Convolution

Question

I am trying to evaluate $c_n = \sum_{k=0}^m {n \choose k}{n-k \choose m-k}$ using binomial convolution. I know that this can be written as $c_n = \sum_{k=0}^m {m \choose k}{n \choose m}$. I also know that for some sequences $a_n,b_n$, $a_n*b_n = {n \choose m}$ from binomial convolutions. Beyond this I don't know what it means to evaluate $c_n$.

Answer 1

The idea is that if we have two exponential generating functions $$f(z) = \sum_{k=0}^\infty a_k \frac{z^k}{k!}, \quad g(z) = \sum_{k=0}^\infty b_k \frac{z^k}{k!},$$ then their product is $$f(z)g(z) = \sum_{k=0}^\infty c_k \frac{z^k}{k!},$$ where $$c_k = \sum_{m=0}^k \binom{k}{m} a_m b_{k-m}$$ is the binomial convolution of their sequences of coefficients. So if we can choose an appropriate pair of sequences $\{a_k\}$ and $\{b_k\}$ such that their convolution is $\{c_k\}$, and the product of their respective EGFs has a "nice" form, then we can obtain an identity for $c_k$. What could you choose?

Answer 2

nCk is simply coefficient of x^k in the expansion (1+x)^n

n-kCm-k is coefficient of x^(m-k) in thr expansion (1+x)^(n-k)

Multiplying both and taking sum of nCk x (n-k)C(m-k) = coefficient of x^m in the expansion (1+x)^(2n-k) which is

2n-kCm