# Multiple sum involving binomial factors

Let $n$ and $m$ be positive integers and let $0 \le j \le n-m-1$. Show that: \begin{align} \sum\limits_{l=m}^{n-j-1} \binom{n-l-1}{j} \binom{l}{m} \binom{n+l}{j} &=\sum\limits_{p=0}^j \sum\limits_{p_1=0}^j \sum\limits_{p_2=0}^m \frac{(p+p_1+p_2)!}{p! p_1! p_2!} \binom{j}{p_1} \binom{2n-j}{j-p}\\\hspace{1cm} &\times\binom{n-j+p}{m-p_2} \binom{n-j-m+p+p_2}{1+p+p_1+p_2} (-1)^{p+p_2} \end{align}

I have derived it using methods from analysis and then I verified the result using Mathematica. This result is a generalisation of another result given in here A double sum with combinatorial factors .

• What are your own ideas? – Jonas Dahlbæk Aug 1 '14 at 14:56
• FYI: I adjusted your Mathjax so that the equation would display without running off the page. Let me know if you'd prefer it differently. – Semiclassical Aug 1 '14 at 15:02
• Great. Thanks for devoting time to my questions. Frankly, I am not good at counting'' proofs of such identities. I just derive all that using standard tricks like $\left. d_x^j/j! x^n \right|_{x=1} = \binom{n}{j}$ and changing the sum into a geometric series. This all works pretty well. – Przemo Aug 1 '14 at 15:04
• @przemo: I'm a fan of generating function methods myself. But I don't really see how to apply them here, hence why I was trying to spot a counting approach. (BTW, if you want your comments here to be forwarded to me, include "@Semiclassical" somewhere in the text.) – Semiclassical Aug 1 '14 at 21:06
• @Semiclassical I have presented the way I derived the result below. Yet, I am still dissatisfied with it. I was expecting to obtain a closed form solution and instead I have a nasty bunch of sums. I think that the sums on the right hand side still need to be simplified. Thank you very much for the attention you devote to my problems. – Przemo Aug 5 '14 at 11:00

We consider a following generating function. $$S := \sum\limits_{l=0}^{n-j-1} \binom{n-l-1}{j} \binom{n+l}{j} q^l$$ It is readily seen that the $m$th derivative of our generating function at $q=1$, that derivative divided by $m!$, yields the sum in question. Now we have:
\begin{eqnarray} S &=& \left.\frac{1}{(j!)^2} \frac{d^j}{d x^j} \frac{d^j}{d y^j} \sum\limits_{l=0}^{n-j-1} \left( x^{n-l-1} y^{n+l} q^l\right)\right|_{x=1,y=1} \\ &=& \left.\frac{1}{(j!)^2} \frac{d^j}{d x^j} \frac{d^j}{d y^j} \left(\frac{x^n y^n - q^{n-j} x^j y^{2n-j}}{x-qy}\right)\right|_{x=1,y=1} \\ &=& \left.\frac{1}{(j!)^2} \frac{d^j}{d x^j} \sum\limits_{p=0}^j \binom{j}{p} \left(x^n (n)_{(j-p)} y^{n-j+p} - q^{n-j} x^j (2n-j)_{(j-p)} y^{2n-2j+p}\right) \cdot \frac{p!}{(x-q y)^{p+1}} q^p \right|_{x=1,y=1} \\ &=& \left.\sum\limits_{p=0}^j \sum\limits_{p_1=0}^j \binom{p+p_1}{p} \left(\binom{n}{j-p_1} \binom{n}{j-p} x^{n-j+p_1} y^{n-j+p} - q^{n-j} \binom{j}{j-p_1} \binom{2n-j}{j-p} x^{p_1} y^{2 n-2 j+p}\right) \cdot \frac{(-1)^{p_1} q^p}{(x - q y)^{p+p_1+1}}\right|_{x=1,y=1} \\ &=& \sum\limits_{p=0}^j \sum\limits_{p_1=0}^j \binom{p+p_1}{p} \left(\binom{n}{j-p_1} \binom{n}{j-p} q^p - \binom{j}{j-p_1} \binom{2n-j}{j-p} q^{n-j+p}\right) \cdot \frac{(-1)^{p_1} }{(1-q)^{p+p_1+1}} \end{eqnarray} What we have done above is, firstly we expressed our sum through a geometric series, secondly we summed up those series, thirdly we computed the derivative with respect to $x$ using the chain rule, fourthly we computed the derivative with respect to $y$ using the chain rule. Finally we took the value at both $x=1$ and $y=1$. Now, we take the $m$-th derivative with respect to $q$. We have:
Now, the only thing we need to do is to take the value of the expression above at $q=1$. Unfortunately the expression becomes indefinite at this value of $q$. Therefore we need to apply the de l'H$\hat{o}$pital's rule. We differentiate both the numerator and the denominator $2j+m+1$ times and then take the value at $q=1$. We have: \begin{eqnarray} \frac{d^m S}{d q^m} &=& \frac{m!}{(-1)^{2j+m+1} (2j+m+1)!} \sum\limits_{p=0}^j \sum\limits_{p_1=0}^j \sum\limits_{p_2=0}^m\sum\limits_{p_3=0}^{2j+m+1} \frac{(p+p_1+p_2)!}{p! p_1! p_2!} \binom{2j+m+1}{p_3} \\ &&\left(\binom{n}{j-p_1} \binom{n}{j-p} \binom{p}{m-p_2} (p+p_2-m)_{(2j+m+1-p_3)} q^{p+p_2+p_3-2j-2m-1} - \binom{j}{j-p_1} \binom{2n-j}{j-p} \binom{n-j+p}{m-p_2} (p+p_2+n-m-j)_{(2j+m+1-p_3)} q^{p+p_2+p_3+n-3 j- 2 m-1}\right) \cdot (-1)^{p_1+p_3} (m+ 2 j+1 -p - p_1-p_3)_{(p_3)} (1-q)^{m+2 j - p-p_1-p_2-p_3} \end{eqnarray} Now we are ready to take the value at $q=1$ because nothing is indefinite anymore. We clearly see that the power of $(1-q)$ factor on the right-hand-side produces a Kronecker delta function and imposes the condition $p+p_1+p_2+p_3=2 j+m$. From the two terms in the round brackets the first term vanishes. Indeed, for the first term to be non-zero we must have $p+p_2-m \ge p+p_1+p_2$ which is equivalent to $0 \ge m+p_1$ and is false. Therefore we arrive at the final result: \begin{eqnarray} \left.\frac{d^m S}{d q^m}\right|_{q=0} &=& (-1)^{m+2} m! \sum\limits_{p=0}^j \sum\limits_{p_1=0}^j \sum\limits_{p_2=0}^m \\ &&\frac{(p+p_1+p_2)!}{p! p_1! p_2!} \binom{j}{p_1} \binom{2n-j}{j-p} \binom{n-j+p}{m-p_2} \binom{n-j-m+p+p_2}{1+p+p_1+p_2} (-1)^{2j+m-p-p_2} \end{eqnarray} This is the final result. Now we simplify this result. Without loss of generality we set $j = n-m-\theta$. Using Mathematica we do the sum over $p_2$. Indeed we have: $$\sum\limits_{p_2=0}^m \binom{p+p_1+p_2}{p_2} \binom{m+\theta+p}{m-p_2} \binom{\theta+p+p_2}{1+p+p_2+p_1} (-1)^{p_2} = \binom{m+p+\theta}{1+m+p+p_1}$$ Therefore we have: $$\frac{1}{m!} \left.\frac{d^m S}{d q^m} \right|_{q=1} = \sum\limits_{p=0}^j \binom{2 n-j}{j-p} (-1)^p \sum\limits_{p_1=0}^j \binom{p+p_1}{p_1} \binom{j}{p_1} \binom{m+p+\theta}{1+m+p+p_1}$$
In summary we have established the following three identities: \begin{eqnarray} \sum\limits_{l=m}^{n-j-1} \binom{n-l-1}{j} \binom{l}{m} \binom{n+l}{j} &=& \\ \binom{2n-j}{j} \frac{1}{(1+n+m)^{(n-m-j)}} \left[ \sum\limits_{l=m}^{n-j-1} \binom{n-l-1}{j} \binom{n+l}{l-m} l_{(l-m)}(2n-2j)_{(n-j-l)} \right] &=& \\ \sum\limits_{p=0}^j \binom{2 n-j}{j-p} (-1)^p \sum\limits_{p_1=0}^j \binom{p+p_1}{p_1} \binom{j}{p_1} \binom{n+p-j}{1+m+p+p_1} \end{eqnarray} Here $n=1,2,3,\cdots$ and $m=0,\cdots,n-1$ and $j=0,\cdots,n-m-1$.