# Sum of products of binomials

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.

• If I computed it correctly (please recheck), then $S(12,13) = 3 \cdot 101 \cdot 1370899$ for $k = \min\{a,b\} = 12$. It thus looks impossible to me to provide any product formula not involving any sum. (Looking for big prime factors is my first test to check to hope for product formulas.) Feb 19, 2018 at 11:33
• Using Leibnitz' formula one has $$S(a,b)=\sum_{j=0}^{\min(a,b)}(-1)^j\binom{k+b-j}{k}\binom{a}{j}2^{a-j}$$ but I don't know if that helps. Feb 19, 2018 at 12:07
• The sum is good for computing determinants because det(AB)=(det A)(det B). Feb 19, 2018 at 13:44
• You can use Petkovšek's algorithm (en.wikipedia.org/wiki/Petkovšek%27s_algorithm) to prove that there is no closed form for the sum. Feb 20, 2018 at 2:06
• @ZachTeitler you are right, the question as I wrote it suggests your answer. In my mind I was hoping some interpretations with lattice paths or graphs, but I guess I can figure it out using the obvious combinatorial interpretation. I upvote you because it actually helped! IraGessel that's amazing! Abdelmalek I don't bother you with my actual matrix, but it is not the product of two matrices with easier determinants. Thank you all anyway! Feb 20, 2018 at 13:46

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

• Thank you for answering. It is pretty disappointing, that even for b=0 there is no simple answer for general a. I think this shatters the hope for a closed formula. Feb 19, 2018 at 17:43
• @Simone Melchiorre Chiarello: Maple and Mathematica derive a closed-form expression for the sum under considerarion. This is a technical stuff. Did you look at my answer before commenting? Feb 19, 2018 at 17:47
• @user64494 "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. " Feb 19, 2018 at 17:55
• @Simone Melchiorre Chiarello: Are you serious? But you wrote in the question "but rather in an expression that does not involve a summation, like the ones before ". Feb 19, 2018 at 17:59
• Dear user64494, I looked at your answer, but I don't consider it very useful. Indeed, checking the definition of hypergeometric functions, this is little more than rewriting the definition. You could write up hypergeometric functions even for other (simpler) identities involving sums of products of binomials, although you might have a simple answer like the one in Vandermonde-Chu identity. I hoped some simple formula existed also for my sum, but apparently it is hopeless. Probably a combinatorial interpretation would be preferrable at this point. Feb 19, 2018 at 19:29

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.

• Thank you for the answer! Actually, this is exactly what I was looking for: I will now try to use Viennot's theory to (try to) interpret my determinants as number of non-intersecting paths: I don't think it will be hard, since I am not really interested in counting them, but just to say that my determinants are non-zero. Thank you again, you really made my day! :) Feb 24, 2018 at 19:51

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{_2F_1}(-k,b+1;\,a-k+1;\,-1)}$$ I think both answers are equivalent.