A Binomial Identity simplify

I want to symplify $$ \sum_{\ell=1}^{k} \frac{1}{\ell}\sum_{m=1}^{\min\{\ell,k-\ell\}}\binom{\ell}{m}\binom{k-\ell-1}{m-1}. $$

Too long for a comment. It is advantageous to write your quantity as:

$$ c_{ij}^k =k\sum_{\ell=1}^{k-1}\sum_{m=0}^{\ell}\sum_{c=0}^m\frac{1}{\ell} \left(-1\right)^{\ell-i} \binom{\ell}{m}\binom{k-\ell-1}{m-1}\binom{m}{c} \binom{k-2m}{i + j -2c -\ell}\binom{m}{\ell+c-i}, $$ where $k$ is assumed to be larger than $1$.

According to numerical experiments the quantity can be expressed by the following closed form:

$$ c_{ij}^k=\begin{cases} \hphantom{-}\binom{k}{i},& j=0\text{ or } j=k,\ 1\le i\le k-1;\\ -\binom{k}{j},& i=0\text{ or } i=k,\ 1\le j\le k-1;\\ \hphantom{-}\hphantom{-}0,& \text{in all other cases}, \end{cases}\tag1 $$ which can be written in one line as: $$ c_{ij}^k=(\delta_{j0}+\delta_{jk})\binom ki-(\delta_{i0}+\delta_{ik})\binom kj.\tag2 $$

Hope, this can help.

Here is some information for odd $k=2K+1$ regarding a more symmetric representation which could be somewhat easier to show. A similar approach might work for the even case. We split \begin{align*} \sum_{l=1}^{2K}&\frac{(-1)^l}{l}\sum_{m=1}^{\min\{l,2K+1-l\}}\binom{l}{m}\binom{2K-l}{m-1} \sum_{c=0}^m\binom{m}{c}\binom{2K+1-2m}{i+j-2c-l}\binom{m}{l+c-i}\\ &=\sum_{l=1}^{K}\frac{(-1)^l}{l}\sum_{m=1}^{l}\binom{l}{m}\binom{2K-l}{m-1} \sum_{c=0}^m\binom{m}{c}\binom{2K+1-2m}{i+j-2c-l}\binom{m}{l+c-i}\tag{1}\\ &\quad+ \sum_{l=K+1}^{2K}\frac{(-1)^l}{l}\sum_{m=1}^{2K+1-l}\binom{l}{m}\binom{2K-l}{m-1} \sum_{c=0}^m\binom{m}{c}\binom{2K+1-2m}{i+j-2c-l}\binom{m}{l+c-i}\tag{2}\\ \end{align*}

and transform the second sum (2) to get a representation which is nearly the same as the sum (1) multiplied by $-1$.

We obtain from (2) \begin{align*} \sum_{l=K+1}^{2K}&\frac{(-1)^l}{l}\sum_{m=1}^{2K+1-l}\binom{l}{m}\binom{2K-l}{m-1} \sum_{c=0}^m\binom{m}{c}\binom{2K+1-2m}{i+j-2c-l}\binom{m}{l+c-i}\\ &=\sum_{l=1}^{K}\frac{(-1)^{l+K}}{l+K}\sum_{m=1}^{K+1-l}\binom{l+K}{m}\binom{K-l}{m-1}\\ &\qquad\cdot\sum_{c=0}^m\binom{m}{c}\binom{2K+1-2m}{i+j-2c-l-K}\binom{m}{l+K+c-i}\tag{3}\\ &=\sum_{l=1}^{K}\frac{(-1)^{l+1}}{2K+1-l}\sum_{m=1}^{l}\binom{2K+1-l}{m}\binom{l-1}{m-1}\\ &\qquad\cdot\sum_{c=0}^m\binom{m}{c}\binom{2K+1-2m}{i+j-2c+l-2K-1}\binom{m}{2K+1-l+c-i}\tag{4}\\ &=\sum_{l=1}^{K}\frac{(-1)^{l+1}}{l}\sum_{m=1}^{l}\binom{2K-l}{m-1}\binom{l}{m}\\ &\qquad\cdot\sum_{c=0}^m\binom{m}{c}\binom{2K+1-2m}{i+j-2c+l-2K-1}\binom{m}{2K+1-l+c-i}\tag{5}\\ \end{align*}

Comment:

• In (3) we shift the index $l$ by $K$ to start with $l=1$.

• In (4) we change the order of summation of the outer sum $l\to K+1-l$.

• In (5) we use the binomial identity $\binom{p}{q}=\frac{p}{q}\binom{p-1}{q-1}$ and transform $\frac{1}{2K+1-l}\binom{2K+1-l}{m}=\frac{1}{m}\binom{2K-l}{m-1}$ followed by $\frac{1}{m}\binom{l-1}{m-1}=\frac{1}{l}\binom{l}{m}$.

Numerical calculation indicates the sum (5) is equal to (1) times $-1$.

By putting (1) and (5) together we conclude OPs claim for odd $k=2K+1$ is equivalent with showing for $1\leq i,j\leq 2K$: \begin{align*} &\color{blue}{\sum_{l=1}^{K}\frac{(-1)^l}{l}\sum_{m=1}^{l}\binom{l}{m}\binom{2K-l}{m-1} \sum_{c=0}^m\binom{m}{c}}\\ &\ \ \color{blue}{\cdot\left[\binom{2K+1-2m}{i+j-2c-l}\binom{m}{l+c-i}-\binom{2K+1-2m}{i+j-2c+l-2K-1}\binom{m}{2K+1-l+c-i}\right]}\\ &\ \ \color{blue}{=0}\tag{6} \end{align*}

Add-on 2019-07-07: Two aspects.

Up to now I couldn't find an answer but here is some additional information which might be helpful when looking for an answer. Using the coefficient of operator $[z^n]$ to denote the coefficient of $z^n$ of a (formal Laurent) series $A(z)$ we can write for instance \begin{align*} [z^k](1+z)^n=\binom{n}{k}\tag{7} \end{align*}

This notation (7) is strongly related with Egorychev's method $$\mathop{res}_z\frac{A(z)}{z^{M+1}}=[z^{-1}]z^{-M-1}A(z)=[z^M]A(z)$$ where many great examples can be found in his book Integral Representation and the Computation of Combinatorial Sums.

• We can transform the inner sum of (1) to \begin{align*} \sum_{c=0}^m&\binom{m}{c}\binom{2K+1-2m}{i+j-2c-l}\binom{m}{l+c-i}\\ &=\sum_{c=0}^m\binom{m}{c}[z^{i+j-2c-l}](1+z)^{2K+1-2m}[u^{l+c-i}](1+u)^m\\ &=[z^{i+j-l}](1+z)^{2K+1-2m}[u^{l-i}](1+u)^m\sum_{c=0}^m\binom{m}{c}\left(\frac{z^2}{u}\right)^c\\ &=[z^{i+j-l}](1+z)^{2K+1-2m}[u^{l-i}](1+u)^m\left(1+\frac{z^2}{u}\right)^m\\ \end{align*} Similarly transforming (5) we obtain \begin{align*} \sum_{c=0}^m&\binom{m}{c}\binom{2K+1-2m}{i+j-2c+l-2K-1}\binom{m}{2K+1-l+c-i}\\ &=\sum_{c=0}^m\binom{m}{c}[z^{i+j-2c+l-2K-1}](1+z)^{2K+1-2m}[u^{2K+1-l+c-i}](1+u)^m\\ &=[z^{i+j+l-2K-1}](1+z)^{2K+1-2m}[u^{2K+1-l-i}](1+u)^m\sum_{c=0}^m\binom{m}{c}\left(\frac{z^2}{u}\right)^c\\ &=[z^{i+j+l-2K-1}](1+z)^{2K+1-2m}[u^{2K+1-l-i}](1+u)^m\left(1+\frac{z^2}{u}\right)^m\\ &=[z^{i+j-l}](1+z)^{2K+1-2m}[u^{l-i}](1+u)^m\left(1+\frac{z^2}{u}\right)^m\left(\frac{z}{u}\right)^{2K+1-l}\\ \end{align*}

  Putting all together we obtain analogously to (6) OP's claim for odd $k=2K+1$ is equivalent with showing that \begin{align*} &\color{blue}{[z^{i+j}u^{-i}](1+z)^{2K+1}\sum_{l=1}^{K}\frac{(-1)^l}{l}\left(\frac{z}{u}\right)^{l}\left(1-\left(\frac{z}{u}\right)^{2K+1-2l}\right)}\\ &\qquad\color{blue}{\cdot\sum_{m=1}^{l}\binom{l}{m}\binom{2K-l}{m-1} \left(\frac{1+u}{1+z}\right)^m\left(1+\frac{z^2}{u}\right)^m =0}\tag{8}\\ \end{align*}

  Note that in (8) the factor $(1+z)^m$ in the denominator can be cancelled due to $(1+z)^{2K+1}$ as well as the factors $u^{p}$ in the denominator can be merged into the coefficient of operator. So, we are comparing coefficients of a bivariate polynomial in $z$ and $u$. We have a situation similar to (6) but it is not easy to see how this can be simplified in order to show the claim.

• We take a look at (6) again and write the claim as \begin{align*} &\sum_{l=1}^{K}\frac{(-1)^l}{l}\sum_{m=1}^{l}\binom{l}{m}\binom{2K-l}{m-1}\\ &\qquad\cdot\sum_{c=0}^m\binom{m}{c}\binom{2K+1-2m}{i+j-2c-l}\binom{m}{l+c-i}\\ &=\sum_{l=1}^{K}\frac{(-1)^l}{l}\sum_{m=1}^{l}\binom{l}{m}\binom{2K-l}{m-1}\\ &\qquad\cdot\sum_{c=0}^m\binom{m}{c}\binom{2K+1-2m}{i+j-2c+l-2K-1}\binom{m}{2K+1-l+c-i}\\ \end{align*} Calculations for small values of $1\leq i,j\leq 2K$ show the number of non-zero terms of the LHS and of the RHS differ. This indicates that a detailed analysis of the variable range of the LHS which give non-zero terms: \begin{align*} &1\leq l\leq m\\ &0\leq m-1\leq 2K-l\\ &0\leq i+j-2c-l\leq 2K+1-2m\\ &0\leq l+c-i\leq m \end{align*} and similarly inspection of the variable range of the RHS might give indications of nice linear transformations of index variables. This way we could transform LHS and RHS to get simpler representations from which the claim can be derived easily. Alas, due to the rather complicated relationship of the index variables this job looks cumbersome.