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 .

  • $\begingroup$ What are your own ideas? $\endgroup$ – Jonas Dahlbæk Aug 1 '14 at 14:56
  • $\begingroup$ 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. $\endgroup$ – Semiclassical Aug 1 '14 at 15:02
  • $\begingroup$ 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. $\endgroup$ – Przemo Aug 1 '14 at 15:04
  • $\begingroup$ @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.) $\endgroup$ – Semiclassical Aug 1 '14 at 21:06
  • $\begingroup$ @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. $\endgroup$ – Przemo Aug 5 '14 at 11:00

We consider a following generating function. \begin{equation} S := \sum\limits_{l=0}^{n-j-1} \binom{n-l-1}{j} \binom{n+l}{j} q^l \end{equation} 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:

\begin{eqnarray} \frac{d^m S}{d q^m} &=& \sum\limits_{p=0}^j \sum\limits_{p_1=0}^j \sum\limits_{p_2=0}^m \binom{p+p_1}{p_1} \binom{m}{p_2} \\ &&\left( \binom{n}{j-p_1} \binom{n}{j-p} (p)_{(m-p_2)} q^{p+p_2-m} - \binom{j}{j-p_1} \binom{2n-j}{j-p} (n-j+p)_{(m-p_2)} q^{p+p_2+n-m-j} \right) \cdot (-1)^{p_1} \frac{(p+p_1+1)^{(p_2)}}{(1-q)^{p+p_1+p_2+1}} \end{eqnarray}

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: \begin{equation} \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} \end{equation} Therefore we have: \begin{equation} \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} \end{equation}

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

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.