Interesting combinatorial identities

Question

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.

Answer 1

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.

Answer 2

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.