1
$\begingroup$

Let $n$ be a strictly positive integer and let $j=0,\dots,n-1$. By using Mathematica I managed to guess the following identities: \begin{eqnarray} \sum\limits_{m=0}^{n-j-1} \binom{n-m-1}{j} \binom{n+m}{j} &=& \frac{1}{2} \binom{2 n}{2j + 1} \\ \sum\limits_{m=0}^{n-j-1} \binom{n-m-1}{j} \binom{n+m+1}{j+1} &=& \frac{1}{2} \binom{2 n+1}{2j + 2} + \binom{n-1}{j} \binom{n+1}{j+1} \frac{n(n-j)}{2 (n+1)(j+1)} \\ \sum\limits_{m=0}^{n-j-1} \binom{n-m-1}{j} \binom{n+m+2}{j+2} &=& \frac{1}{2} \binom{2 n+2}{2j + 3} + \binom{n-1}{j} \binom{n+2}{j+2} \frac{n(n-j)}{(n+2)(j+1)} \\ \sum\limits_{m=0}^{n-j-1} \binom{n-m-1}{j} \binom{n+m+3}{j+3} &=& \frac{1}{2} \binom{2 n+3}{2j + 4} + \binom{n-1}{j} \binom{n+3}{j+3} \frac{n(n-j)(11+5 j+(7+3 j) n)}{(n+2)(n+3)(4+ 2j)(j+1)} \\ \sum\limits_{m=0}^{n-j-1} \binom{n-m-1}{j} \binom{n+m+4}{j+4} &=& \frac{1}{2} \binom{2 n+4}{2j + 5} + \binom{n-1}{j} \binom{n+4}{j+4} \frac{2 n(n-j)(5+2 j+(3+ j) n)}{(n+3)(n+4)(2+ j)(j+1)} \\ \sum\limits_{m=0}^{n-j-1} \binom{n-m-1}{j} \binom{n+m+5}{j+5} &=& \frac{1}{2} \binom{2 n+5}{2j + 6} + \binom{n-1}{j} \binom{n+5}{j+5} \cdot \\ &&\frac{n(n-j)((137+93 j+16 j^2)+(264+161j+25 j^2)n/2+(62+35 j+ 5 j^2)n^2/2)}{(n+3)(n+4)(n+5)(j+1)(j+2)(j+3)} \end{eqnarray} The temptation is strong to write a general conjecture: \begin{equation} \sum\limits_{m=0}^{n-j-1} \binom{n-m-1}{j} \binom{n+m+a}{j+a} = \frac{1}{2} \binom{2 n+a}{2j + 1+a} + \binom{n-1}{j} \binom{n+a}{j+a} \cdot\left(\cdots\right) \end{equation} Can anyone advise me how to tackle such a problem?. I think that in this particular case the method of generating functions does not lead to a closed form result.

$\endgroup$
0
$\begingroup$

Hint: The first identity can be explained as follows.

One wants to count how many sequences $a_1<\cdots<a_{2j+1}$ can be formed from $\{1,\dots,2n\}$. Of course the standard answer is ${2n}\choose{2j+1}$.

Let's count differently by looking at the middle number $a_{j+1}$. It can only take one of the values $j+1,\dots, 2n-j$.

For each $k=j+1,\dots,2n-j$, there are ${k-1}\choose j$ choices of $a_1<\cdots<a_j$ and ${2n-k}\choose{j}$ choices of $a_{j+2}<\cdots<a_{2j+1}$. That gives $${{2n}\choose{2j+1}}=\sum^{2n-j}_{k=j+1} {{k-1}\choose{j}} {{2n-k}\choose{j}}.$$

Reindexing, we get $$\begin{aligned}{{2n}\choose{2j+1}}&=\sum^{2n-j-1}_{k=j} {{k}\choose{j}} {{2n-k-1}\choose{j}}\\&=\sum_{k=j}^{n-1}\binom{k}{j}\binom{2n-k-1}{j}+\sum^{2n-j-1}_{k=n}\binom{k}{j}\binom{2n-k-1}{j}. \end{aligned}$$ Now each of the last sums is equal to the LHS by another reindexing.

$\endgroup$
  • $\begingroup$ Thank you very much for that. This is very nice but cannot see how this can be extended to the other sums. If I replace the sequence in question by $a_1 < \cdots < a_{2j+1+a}$ from $\left\{1,\cdots,2n+a\right\}$ and again, look at the values of $a_{j+1}$ the same way as you did it in here I will arrive at the following idenity: \begin{equation} \binom{2n+a}{2j+1+a} = \sum\limits_{k=0}^{n-j-1} \binom{n-1-k}{j} \binom{n+k}{j+a} + \sum\limits_{k=0}^{n-j-1} \binom{n-1-k}{j+a} \binom{n+k}{j}\end{equation}. this is still very much different from what I have above. $\endgroup$ – Przemo Aug 8 '14 at 10:11
1
$\begingroup$

We provide a closed form expression for our sum. \begin{eqnarray} &&\sum\limits_{m=0}^{n-j-1} \binom{n-m-1}{j} \binom{n+m+a}{j+a}=\\ && \!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\binom{a+2 n}{a+2 j+1}-\binom{a+n}{a+j+1} \binom{a+2 n}{j} \, \cdot _3F_2(-j,a+j+1,a+n+1;a+j+2,a-j+2 n+1;1) =\\ && \!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\binom{a+2 n}{a+2 j+1}-\binom{a+n}{a+j+1} \binom{-j+2 n-1}{j} \, \cdot _3F_2(-j,a+j+1,j-n+1;a+j+2,j-2 n+1;1) \end{eqnarray} We obtained this result by expanding the first binomial factor on the left hand side into a linear combination of binomial factors that are "adjacent" to the second binomial factor , then absorbing the resulting binomial factors into the second binomial factor and finally doing the sum over $m$ using the telescoping property of the binomial factor. Note that the hypergeometric function on the right hand side is a rational function in $n$.

Note: Interestingly enough Gosper's algorithm fails on this sum. If I have time I will explain why this is the case.

$\endgroup$

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.