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}.$$

• I'd say try generating functions, but then again that strikes me as the likely origin of the identities in the first place. Care to elaborate on context? Jun 30 '19 at 3:37
• Hi this is a coefficient of a polynomial. I tried generating function but it does not help, since the summation is finite and there is an extra term $\ell$. Jun 30 '19 at 4:20
• @SophieLL How did you obtain $c_{ij}$? Where it´s from? Jul 3 '19 at 1:08
• They are coefficients of a polynomial. Jul 3 '19 at 15:10
• Why did you completely change the question?
– user
Aug 3 '21 at 14:33

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.

• Thank you so much! I have proved for the other two cases but the zero cases >< Jul 2 '19 at 23:50
• The zero case is so hard to prove... Jul 2 '19 at 23:52
• @SophieLL It would be useful if you include in your question the proof of the "non-zero" case. Besides, the formulation of the problem in your question is a little bit misleading, as $c_{ij}^k=0$ in almost all cases and not only if both inequalities $1\leq i \leq k-1$, and $1\leq j\leq k-1$ are satisfied.
– user
Jul 2 '19 at 23:59
• actually, for i=0, or j=0, it is not zero either, but these are trivial. The only zeros should be cases when i and j both equal to 0 or both equal to k, and the case I mentioned above. Jul 3 '19 at 0:02

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*}

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.

• Hi, @markusscheuer, thank you so much for helping me!!! However, I am still confused about why (5) is equal to - (1). Do you mind illustrating a little bit more on this? Jul 5 '19 at 1:22
• I think if we replace $\ell$ as $2k-\ell+1$, we can still get (5), but it is not obvious how we can show that (5)=-(1), since $1 \le \ell \le K$ in the above setting >< Jul 5 '19 at 3:27
• @SophieLl: I know it's just a first step simplifying the upper limit of the sum with index $m$. It looks promising that the part (1) and (5) are the same besides a factor $-1$. But, admittedly this main step is left open and has to be shown. I'll work on it at the weekend. Jul 5 '19 at 4:46
• Thank you so much! I am still working on trying other ways to show, but still don't know how to show it. Jul 7 '19 at 1:05
• @SophieLL: I'm sorry, but despite a considerable amount of time I've tried to find a solution I wasn't successful. Jul 7 '19 at 6:00

By way of an extended comment in response to a pers. comm. / request. A conjectured alternate representation of the sum (here $$i=p$$ and $$j=q$$) is given by

$$k (-1)^p \mathrm{Res}_{z=0} z^{p-1} [w^{p+q}] (1+w)^{k} [v^{k}] (1+v)^{k-1} \\ \times \sum_{\ell\ge 1} \frac{(-1)^\ell}{\ell} z^{-2\ell} w^\ell (1+w)^{-2\ell} v^\ell (1+v)^{-\ell} (z(1+w)^2+v(1+z)(z+w^2))^\ell.$$

At this point the term in $$1/\ell$$ introduces a logarithm and the power term in $$\ell$$ does not factorize / collect easily in $$z$$ or $$w.$$

• Thank you so much! I totally understand... I have no idea either... Jul 7 '19 at 1:06
• @MarkoRiedel: Many thanks for your support and evaluation. (+1) Jul 7 '19 at 5:58