Closed form for $\sum_{k=0}^{l}\binom{k}{n}\binom{k}{m}$

Question

Does there exist any closed form for the following sum?

$$\sum_{k=0}^{l}\binom{k}{n}\binom{k}{m}$$

Where $l \in \mathbb N$ and $m,n \in \mathbb Z$

---

My try:

$$ \sum_{k=\max\left(m,n\right)}^{l}\binom{k}{n}\binom{k}{m}=\sum_{k=0}^{l}\binom{k}{k-n}\binom{k}{k-m}$$$$=\left(-1\right)^{\left(-n-m\right)}\sum_{k=0}^{l}\binom{-n-1}{k-n}\binom{-m-1}{k-m}$$$$=\left(-1\right)^{\left(-n-m\right)}\sum_{k=0}^{l}\binom{-n-1}{-1-k}\binom{-m-1}{k-m}$$$$=\left(-1\right)^{\left(-n-m\right)}\binom{-n-m-2}{-m-1}$$

$$=\left(-1\right)^{\left(-n-m\right)}\binom{-n-m-2}{-n-1}=\left(-1\right)^{\left(-m-1\right)}\binom{m}{-n-1}$$$$=\left(-1\right)^{\left(-m-1\right)}\binom{m}{m+n+1}=\left(-1\right)^{n}\binom{n}{m+n+1}$$

I'm not sure whether it's right, so can someone verify the solution, and if it's not right then please provide a closed form (of course if that's exist).

Answer 1

I guess the best that you can get when $0 \le n \le m$ is in table III, page 15, eq. (4.9) of Gould's combinatorial identities:

$$\sum_{k=0}^{l}{k \choose n}{k \choose m} = \sum_{k=0}^{n}{n \choose k}{m \choose k}{l+k+1 \choose n+m+1}$$

I don't know whether that can be extended to $m,n \in \mathbb Z$.

As remarked there, the original source is “The class of the free metabelian group with exponent $p^2$”, by S. Bachmuth and H. Y. Mochizuki, Communications on Pure and Applied Math., Vol. 21 (1968), pp. 385-399.

Answer 2

I doubt there is closed form, but this is another identity which can be derived by contour integration $$\sum_{k=0}^l {k \choose m} {k \choose n} = \sum_{k=0}^n (-1)^k {l+1 \choose m+k+1}{l-k \choose n-k} \, .$$ If you are interested I can write it down. It is useful when $l$ is large and either $m$ or $n$ is small.

edit: On part of your try the third row is still correct, while the fourth equality (first time no sum) is wrong.

Answer 3

Maxima says there is no closed form.

load(zeilberger);
GosperSum(binomial(k, n) * binomial(k, m), k, 0, l);

gives NON GOSPER SUMMABLE

Answer 4

We present a proof of the identity by @Diger, which should be considered a starting point for additional simplification. We seek to show that

$$\sum_{k=0}^l {k\choose m} {k\choose n} = \sum_{k=0}^n (-1)^k {l+1\choose m+k+1} {l-k\choose n-k}.$$

The RHS is

$$[z^n] \sum_{k=0}^n (-1)^k {l+1\choose m+k+1} z^k (1+z)^{l-k}.$$

The coefficient extractor enforces the range:

$$[z^n] \sum_{k\ge 0} (-1)^k {l+1\choose l-m-k} z^k (1+z)^{l-k} \\ = [z^n] (1+z)^l [w^{l-m}] (1+w)^{l+1} \sum_{k\ge 0} (-1)^k w^k z^k (1+z)^{-k} \\ = [z^n] (1+z)^l [w^{l-m}] (1+w)^{l+1} \frac{1}{1+wz/(1+z)} \\ = [z^n] (1+z)^{l+1} [w^{l-m}] (1+w)^{l+1} \frac{1}{1+z+wz} \\ = [z^n] (1+z)^{l+1} [w^{l-m}] (1+w)^{l+1} \frac{1}{1+z(1+w)} \\ = [z^n] (1+z)^{l+1} [w^{l-m}] \sum_{k\ge 0} (-1)^k z^k (1+w)^{k+l+1} \\ = [z^n] (1+z)^{l+1} \sum_{k\ge 0} (-1)^k z^k {k+l+1\choose l-m}.$$

This is

$$\bbox[5px,border:2px solid #00A000]{ \sum_{k=0}^n (-1)^k {l+1\choose n-k} {k+l+1\choose l-m}.}$$

The LHS is

$$\sum_{k\ge 0} [[0\le k\le l]] [z^m] (1+z)^k [w^n] (1+w)^k \\ = [z^m] [w^n] \sum_{k\ge 0} (1+z)^k (1+w)^k [v^l] \frac{v^k}{1-v} \\ = [z^m] [w^n] [v^l] \frac{1}{1-v} \sum_{k\ge 0} (1+z)^k (1+w)^k v^k \\ = [z^m] [w^n] [v^l] \frac{1}{1-v} \frac{1}{1-(1+z)(1+w)v} \\ = [z^m] [w^n] [v^l] \frac{1}{v-1} \frac{1/(1+z)/(1+w)}{v-1/(1+z)/(1+w)}.$$

The inner term is

$$\mathrm{Res}_{v=0} \frac{1}{v^{l+1}} \frac{1}{v-1} \frac{1/(1+z)/(1+w)}{v-1/(1+z)/(1+w)}.$$

Residues sum to zero and the residue at infinity in $v$ is zero. The contribution from minus the residue at $v=1/(1+z)/(1+w)$ is

$$- [z^m] (1+z)^{l+1} [w^n] (1+w)^{l+1} \frac{1/(1+z)/(1+w)}{1/(1+z)/(1+w)-1} \\ = - [z^m] (1+z)^{l+1} [w^n] (1+w)^{l+1} \frac{1/(1+z)}{1/(1+z)-(1+w)} \\ = [z^m] (1+z)^{l+1} [w^n] (1+w)^{l+1} \frac{1/(1+z)}{w+z/(1+z)} \\ = [z^m] (1+z)^{l+1} [w^n] (1+w)^{l+1} \frac{1/z}{w(1+z)/z+1}.$$

Now with $l,m,n$ positive integers we must have $l\ge n,m$ or else there is no contribution to $k^\underline{m} k^\underline{n}.$ This means we continue with

$$[z^m] (1+z)^{l+1} \sum_{k=0}^n {l+1\choose k} \frac{1}{z} (-1)^{n-k} \frac{(1+z)^{n-k}}{z^{n-k}} \\ = \sum_{k=0}^n (-1)^{n-k} {l+1\choose k} {l+1+n-k\choose m+1+n-k}.$$

This is $$\bbox[5px,border:2px solid #00A000]{ \sum_{k=0}^n (-1)^{n-k} {l+1\choose k} {l+1+n-k\choose l-m}.}$$

We have the same closed form for LHS and RHS, thus proving the claim.

For a full proof we also need to show that the contribution from $v=1$ is zero. We get

$$[z^m] [w^n] \frac{1/(1+z)/(1+w)}{1-1/(1+z)/(1+w)} = [z^m] [w^n] \frac{1}{(1+z)(1+w)-1} \\ = [z^m] [w^n] \frac{1}{z+w+zw} = [z^{m+1}] [w^n] \frac{1}{1+w(1+z)/z} \\ = [z^{m+1}] (-1)^n \frac{(1+z)^n}{z^n} = (-1)^n {n\choose n+m+1} = 0.$$

Answer 5

This can be proved using simple terms, with telescoping series and reccurence. Let $$U_{l,n,m}=\binom{l}{n}-\binom{m}{n}=\sum_{k=l}^{m+1} \binom{k}{n}-\binom{k-1}{n}=\sum_{k=l-1}^{m} \binom{k}{n-1}$$ with $n<=m$ and $l>=m$ and $\sum$ is decreasing.

Let $$V_{l,n}=\sum_{k=n}^{0} (-1)^{k}\binom{l}{k}=\sum_{k=n}^{0} (-1)^{k}\binom{l-1}{k}+\binom{l-1}{k-1}$$ This is a telescoping sum which equals $$V_{l,n}=\binom{l-1}{n}$$ with $k$ positive and $l>=n$ and $\sum$ is decreasing.

Now let $T_{l,n,m}=\sum_{k=l}^{m} \binom{k}{m} \binom{k}{n}$ which is our sum in question.

$$\begin{eqnarray*} T_{l,n,m} & = & \sum_{k=l}^{m} \binom{k}{m} \binom{k}{n} \\ & = & \sum_{k=l}^{m} \binom{k}{m} \binom{l}{n} - \sum_{k=l-1}^{m} \binom{k}{m} \left(\binom{l}{n}-\binom{k}{n}\right) \\ & = & \sum_{k=l}^{m} \binom{k}{m} \binom{l}{n} - \sum_{k=l-1}^{m} \binom{k}{m} U_{l,n,k} \\ & = & \left( \sum_{k=l}^{m} \binom{k}{m} \right) \binom{l}{n} - \sum_{k=l-1}^{m} \binom{k}{m} \left(\sum_{i=l-1}^{k} \binom{i}{n-1} \right)\\ \end{eqnarray*}$$ Switching terms of this sum by writing $k$ in respect of $i$. $$\begin{eqnarray*} T_{l,n,m} & = & \binom{l+1}{m+1} \binom{l}{n} - \sum_{i=l-1}^{m} \binom{i}{n-1} \left(\sum_{k=i}^{m} \binom{k}{m} \right)\\ & = & \binom{l+1}{m+1} \binom{l}{n} - \sum_{i=l-1}^{m} \binom{i}{n-1} \binom{i+1}{m+1} \\ \end{eqnarray*}$$ Until now there is no appearence of reccurence hence we try to write the sum in convenient form with $T$, so let: $$S_{l,n,m}=\sum_{i=l}^{m-1} \binom{i}{n} \binom{i+1}{m}$$ which means $$ T_{l,n,m} = \binom{l+1}{m+1} \binom{l}{n} - S_{l-1,n-1,m+1}$$ We return back to $S$ now: $$\begin{eqnarray*}S_{l,n,m} & = & \sum_{i=l}^{m-1} \binom{i}{n} \binom{i+1}{m}\\ & = & \sum_{i=l}^{m-1} \left(\binom{i+1}{n}-\binom{i}{n-1}\right) \binom{i+1}{m} \\ & = & \sum_{i=l}^{m-1} \left(\binom{i+1}{n}-\binom{i+1}{n-1}+\binom{i}{n-2}\right) \binom{i+1}{m} \\ ...& = & \sum_{i=l}^{m-1} \left(\binom{i+1}{n}-\binom{i+1}{n-1}+...\binom{i+1}{0}\right) \binom{i+1}{m} \\ & = & \sum_{i=l}^{m-1} \left(\binom{i+1}{n}\binom{i+1}{m}\right)-\sum_{i=l}^{m-1}\left(\binom{i+1}{n-1}\binom{i+1}{m}\right)+...\sum_{i=l}^{m-1}\left(\binom{i+1}{0}\binom{i+1}{m}\right) \\ & = & \sum_{i=l+1}^{m} \left(\binom{i}{n}\binom{i}{m}\right)-\sum_{i=l+1}^{m}\left(\binom{i}{n-1}\binom{i}{m}\right)+...\sum_{i=l+1}^{m}\left(\binom{i}{0}\binom{i}{m}\right) \\ & = & T_{l+1,n,m}-T_{l+1,n-1,m}+...T_{l+1,0,m} \\ \end{eqnarray*}$$ So then, we plug directly in $T$ we get: $$\begin{eqnarray*} T_{l,n,m} & = & \binom{l+1}{m+1} \binom{l}{n} - S_{l-1,n-1,m+1} \\ & = & \binom{l+1}{m+1} \binom{l}{n} - T_{l,n-1,m+1}+T_{l,n-2,m+1}-...T_{l,0,m} \\ \end{eqnarray*}$$ The linear deployment of this formula leads to troubled understanding so we just suppose it's right for $n-1$ to $0$ then we prove for $n$. $T_{l,0,m}$ is blatantly true for n=0. $$\begin{eqnarray*} T_{l,n,m} & = & \binom{l+1}{m+1} \binom{l}{n} - T_{l,n-1,m+1}+T_{l,n-2,m+1}-...T_{l,0,m} \\ & = & \binom{l+1}{m+1} \binom{l}{n} - \sum_{k=0} \binom{l-k}{n-1-k} \binom{l+1}{m+2+k} + \sum_{k=0} \binom{l-k}{n-2-k} \binom{l+1}{m+3+k} -... \end{eqnarray*}$$ We note that these sums are lined diagonally therefor we collect them horizontally. $$\begin{eqnarray*} & = & \binom{l+1}{m+1} \binom{l}{n} - \sum_{k=0}^{n-1} (-1)^{k}\binom{l}{n-1-k} \binom{l+1}{m+2} + \sum_{k=0}^{n-2} (-1)^{k}\binom{l-1}{n-2-k} \binom{l+1}{m+3}-... \\ & = & \binom{l+1}{m+1} \binom{l}{n} - \binom{l+1}{m+2} V_{l,n-1} + \binom{l+1}{m+2} V_{l-1,n-2} - ... \\ T_{l,n,m} & = & \binom{l+1}{m+1} \binom{l}{n} - \binom{l+1}{m+2} \binom{l-1}{n-1} + \binom{l+1}{m+3} \binom{l-2}{n-2} - ... \end{eqnarray*}$$

---

The proof by linear expansion takes a lot of space and deep simplifications by Writing $T_{n-1}$ in terms of $T_{n-2},T_{n-3},...T_0$, so the same for $T_{n-2}$ yet for $T_{n-3}$ to finally land in multiple vandermonde correlative forms summed up togather, it's more complicated to be written in latex, I found this transformation about three and half years ago when trying to reduce a PE problem.