Identity involving double sum with factorials

Solution 1:

Re-writing slightly we find

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

We may treat this as polynomials in $x$ and take it to be a positive integer. It then generalizes to complex $x.$ Working with the inner sum we find

$$[z^{n-1}] (1+z)^{n+m-\ell-2} [w^\ell] (1+w)^\ell [v^n] (1+v)^{x+n-1} \\ \times \sum_{k=0}^{n-1} (-1)^{n-k} {n-1\choose k} \frac{z^k}{(1+z)^k} (1+w)^k (1+v)^{-k} \\ = (-1)^n [z^{n-1}] (1+z)^{n+m-\ell-2} [w^\ell] (1+w)^\ell [v^n] (1+v)^{x+n-1} \\ \times \left[ 1-\frac{z(1+w)}{(1+z)(1+v)}\right]^{n-1} \\ = (-1)^n [z^{n-1}] (1+z)^{m-\ell-1} [w^\ell] (1+w)^\ell [v^n] (1+v)^{x} (1+v+vz-wz)^{n-1}.$$

Using $q$ as the index variable we get for the outer sum

$$m \sum_{q=1}^m {m-1\choose q-1} (-1)^q [z^{q-1}] (1+z)^{m-\ell-1} \\ \times [w^\ell] (1+w)^\ell [v^q] (1+v)^{x} (1+v+vz-wz)^{q-1} \\ = m \sum_{q=0}^{m-1} {m-1\choose q} (-1)^{m-q} [z^{m-1}] z^q (1+z)^{m-\ell-1} \\ \times [w^\ell] (1+w)^\ell [v^m] v^q (1+v)^{x} (1+v+vz-wz)^{m-q-1} \\ = m [z^{m-1}] (1+z)^{m-\ell-1} [v^m] (1+v)^{x} [w^\ell] (1+w)^\ell \\ \times \sum_{q=0}^{m-1} {m-1\choose q} (-1)^{m-q} z^q v^q (1+v+vz-wz)^{m-q-1} \\ = - m [z^{m-1}] (1+z)^{m-\ell-1} [v^m] (1+v)^{x} [w^\ell] (1+w)^\ell (wz-1-v)^{m-1}.$$

Expanding the last powered term we obtain

$$- m [z^{m-1}] (1+z)^{m-\ell-1} [v^m] (1+v)^{x} [w^\ell] (1+w)^\ell \\ \times \sum_{p=0}^{m-1} {m-1\choose p} w^p z^p (-1)^{m-1-p} (1+v)^{m-1-p}.$$

For the coefficient extractor in $z$ to return a non-zero value we must have $m-1-p \le m-\ell-1$ (note that with $0\lt \ell\lt m$ the term $(1+z)^{m-\ell-1}$ is finite). This says that $\ell \le p.$ On the other hand the coefficient extractor in $w$ requires $p\le \ell$ (the term $(1+w)^\ell$ is finite as well and we use the residue definition ${\ell\choose \ell-p} = \; \underset{w}{\mathrm{res}}\; \frac{1}{w^{\ell-p+1}} (1+w)^\ell.$) The only $p$ to fulfill both conditions is $p=\ell$ and we find

$$- m [z^{m-1}] (1+z)^{m-\ell-1} [v^m] (1+v)^{x} [w^\ell] (1+w)^\ell \\ \times {m-1\choose \ell} w^\ell z^\ell (-1)^{m-1-\ell} (1+v)^{m-1-\ell} \\ = -m {m-\ell-1\choose m-\ell-1} {x+m-1-\ell\choose m} {\ell\choose \ell-\ell} (-1)^{m-1-\ell} {m-1\choose \ell}.$$

This at last simplifies to

$$m (-1)^{m-\ell} {m-1\choose \ell} {x-\ell+m-1\choose m}$$

which is the claim.