Formula for partial sum of binoms: $\sum_{k=0}^{\lfloor n/2 \rfloor} \binom nk \binom mk$

Question

I am dealing with some expressions containing combinatoric numbers. Does anybody know a formula for this?

$$\displaystyle\sum_{k=0}^{\left\lfloor \dfrac{n}{2} \right\rfloor} \binom{n}{k}\binom{m}{k}$$

Answer 1

Not simple and we need to consider three cases since we do not know the parity of $n$ and what $\left[ \dfrac{n}{2} \right]$ means (floor or ceiling function).

• Suppose that $n$ is odd $(n=2p+1)$ and that $\left[ \dfrac{n}{2} \right]=\left\lfloor \frac{n}{2}\right\rfloor=p$, the expression is $$S_p=\sum_{k=0}^{p} \binom{2p+1}{k}\binom{m}{k}$$ and the result is given by $$S_p=\frac{\Gamma (m+2 p+2)}{\Gamma (m+1) \Gamma (2 (p+1))}-\binom{2 p+1}{p+1} \binom{m}{p+1} \, _3F_2(1,-p,-m+p+1;p+2,p+2;1)$$
• Suppose that $n$ is odd $(n=2p+1)$ and that $\left[ \dfrac{n}{2} \right]=\left\lceil \frac{n}{2}\right\rceil=p+1$, the expression is $$S_p=\sum_{k=0}^{p+1} \binom{2p+1}{k}\binom{m}{k}$$ and the result is given by $$S_p=\frac{\Gamma (m+2 p+2)}{\Gamma (m+1) \Gamma (2 (p+1))}-\binom{2 p+1}{p+2} \binom{m}{p+2} \, _3F_2(1,1-p,-m+p+2;p+3,p+3;1)$$
• If $n$ is even $(n=2p)$, whatever $\left[ \dfrac{n}{2} \right]$ could mean, the expression is $$S_p=\sum_{k=0}^{p} \binom{2p}{k}\binom{m}{k}$$ and the result is given by $$S_p=\frac{\Gamma (m+2 p+1)}{\Gamma (m+1) \Gamma (2 p+1)}-\binom{2 p}{p+1} \binom{m}{p+1} \, _3F_2(1,1-p,-m+p+1;p+2,p+2;1)$$ In all cases, appears the generalized hypergeometric function.

Answer 2

We can find a closed form expression in case $m\leq \left\lfloor\frac{n}{2}\right\rfloor$. We use the coefficient of operator $[z^k]$ to denote the coefficient of $z^k$ in a series. This way we can write for instance \begin{align*} \binom{n}{k}=[z^k](1+z)^n \end{align*}

We obtain for $m\leq \left\lfloor\frac{n}{2}\right\rfloor$: \begin{align*} \color{blue}{\sum_{k=0}^{\left\lfloor\frac{n}{2}\right\rfloor}\binom{n}{k}\binom{m}{k}} &=\sum_{k=0}^m\binom{m}{k}\binom{n}{k}\\ &=\sum_{k=0}^m\binom{m}{k}[z^k](1+z)^n\\ &=[z^0](1+z)^n\sum_{k=0}^m\binom{m}{k}z^{-k}\\ &=[z^0](1+z)^n\left(1+\frac{1}{z}\right)^m\\ &=[z^m](1+z)^{m+n}\\ &\,\,\color{blue}{=\binom{m+n}{m}} \end{align*}