Sum of products of binomials

Question

Sums of products of binomial coefficients often have simpler expression which do not involve any summation. Examples are the elementary $$\sum_{i=0}^k\binom{a}{i}\binom{b}{k-i}=\binom{a+b}{k}$$ or the more complicated $$\sum_{i=0}^{\text{min(a,b)}}\binom{x+y+i}{i}\binom{y}{a-i}\binom{x}{b-i}=\binom{x+a}{b}\binom{y+b}{a}$$ or many others like Vandermonde-Chu identity etc.

I am looking for a similar formula for the following sum $$S(a,b):=\sum_{i=0}^k\binom{a}{k-i}\binom{b+i}{i}$$ where here $k\le a$ and everybody is a positive integer. This expression has arisen to me as a coefficient of $(1+q)^a(1-q)^{-1-b}$ and I am interested in computing determinants of such numbers. Therefore I am not interested in a "generating function" answer, but rather in an expression that does not involve a summation, like the ones before. Alternatively, a natural combinatorial interpretation can also be useful, in order to use Viennot's theory of binomial determinants.

Anybody here familiar with combinatorics can give me any help? Thank you in advance.

Answer 1

Lacking reputation, I am unable to comment. I will add, however, that a closed ("summation-signless") expression is not forthcoming. I will adjust your notation modestly and write $$ S_k(a,b) = \sum_{0\leq i \leq k}{a\choose k-i}{b+i\choose i} $$ for $a,b,k\in \mathbb{N}$ with $k\leq a$.

Let us also write $S_k(a,0) = \sum_{0\leq i \leq k}{a\choose k-i} = \sum_{0\leq i \leq k}{a\choose i}$; when $k<a$, it is well-known that $S_k(a,0)$ (the proper prefix sum of the $a$-th row of Pascal's Triangle) does not admit a closed form.

We begin by writing \begin{alignat}{2} S_k(a,1) &=\sum_{0\leq i \leq k}{a\choose k-i}(i+1)\notag \\ &= \sum_{0\leq i \leq k}{a\choose k-i}i+ S_k(a,0) \notag\\ &= \sum_{1\leq i \leq k}{a\choose k-i}i+ S_k(a,0) \notag\\ &= \sum_{0\leq i \leq k-1}{a\choose k-(i+1)}(i+1)+ S_k(a,0) \notag\\ &= S_{k-1}(a,1)+ S_k(a,0). \notag\\ \end{alignat}

Thus, $S_k(a,0) = S_k(a,1) - S_{k-1}(a,1)$; a closed form for both $S_{k}(a,1)$ and $S_{k-1}(a,1)$ would lead to a closed difference expression for $S_k(a,0)$.

Answer 2

Let $G$ be the (infinite) graph with vertex set $\mathbb{Z}^2$, and the following edges. When $x+y < 0$, the vertex $(x,y)$ has outgoing edges to $(x+1,y)$ and to $(x,y+1)$. When $x+y \geq 0$, the vertex $(x,y)$ has outgoing edges to $(x+1-k,y+k)$ for all $k \geq 0$. That is, to $(x+1,y)$, $(x,y+1)$, $(x-1,y+2)$, and so on. These vertices have infinite outdegree (and when $x+y>0$, infinite indegree) but we will only use finite subgraphs, with finite degrees.

Now the number of directed paths in $G$ from $(-a,0)$ to $(b+1-k,k)$ is equal to $S(a,b)$.

Indeed, each edge in $G$ increases the sum of coordinates $x+y$ by $1$. So every path from $(-a,0)$ to $(b+1-k,k)$ has length $a+b+1$. For a given path, label each of the $a+b+1$ steps by their vertical travel ($0$ for a step east, $1$ for a step north, $2$ for a step in direction $(-1,2)$, etc.). The total of the labels is $k$. The first $a$ steps have labels $0$ or $1$. Subsequent steps have labels $\geq 0$.

The pair $(-a,0)$, $(b+1-k,k)$ may be translated by $(m,-m)$ for any $m$.

In your original question you did not say exactly what determinant you are trying to evaluate. But at least some determinants of values $S(a,b)$ can now be interpreted as counting disjoint path systems in the graph $G$. Well, I don't know how easy it will be to count those paths, but anyway I hope it helps.

Answer 3

Mathematica answers

Sum[Binomial[a, k - i]*Binomial[b + i, i], {i, 0, k},Assumptions -> a >= k | b > 0]

$$\binom{a}{k} \, _2F_1(b+1,-k;a-k+1;-1) $$ Addition. Maple performs

sum(binomial(a, k-i)*binomial(b+i, i), i = 0 .. k)assuming a>=k,b>0

$${a\choose k}{\mbox{$_2$F$_1$}(-k,b+1;\,a-k+1;\,-1)} $$ I think both answers are equivalent.