# Generating function of product of binomial coefficients

Let $$m, n\in \mathbb{N}$$ and $$|x| < 1$$. I look for hints to derive an analytic formula for $$f_{m,n}(x) = \sum_{k \in \mathbb{N}} {n + k \choose k} {m + k \choose k} x^{k}.$$

• Hjalmar Rosengren gave a nice formula for $f_{m,n}(x)$ based on the theory of hypergeometric series. Below I provide a direct elementary proof of the same based on generating series. Commented Nov 22, 2021 at 23:06

This is Gauss' hypergeometric function $$F(n+1,m+1,1;x)$$. You can then apply the huge theory of hypergeometric functions to derive further expressions. For instance, Euler's transformation formula gives the alternative expression $$\frac 1{(1-x)^{m+n+1}}\,F(-m,-n,1;x)=\frac 1{(1-x)^{m+n+1}}\sum_{k=0}^{\min(m,n)}\binom mk\binom nk x^k$$ for the same series as a finite sum.

• Fun fact: If one expands the RHS into powers of $x$, then one gets the equivalent binomial identity $\sum_{p+r=k}\binom{m+n+p}{p}\binom{m}{r}\binom{n}{r}=\binom{m+k}{k}\binom{n+k}{k}$. This identity is due to Surányi (1955), and it appears on Page 17 of Riordan: Combinatorial identities; make the substitution $(k,n,p,q)\mapsto(r,k,m,n)$ there. It provides an alternative proof of the expression for $f_{m,n}(x)$ in this post. Commented Nov 22, 2021 at 15:43
• @GHfromMO Unsurprisingly, the identity you attribute to Surányi is also a special case of a classical hypergeometric identity, namely, the Pfaff-Saalschütz summation. I believe Pfaff found it in the late 1700s. Commented Nov 22, 2021 at 15:58
• I'm reminded of the following quotation of Richard Askey (The work of George Andrews: a Madison perspective, 1999): "For years I had been trying to point out that the rather confused world of binomial coefficient summations is best understood in the language of hypergeometric series identities. Time and again I would find first-rate mathematicians who had never heard of this insight and who would waste considerable time proving some apparently new binomial coefficient summation which almost always turned out to be a special case of one of a handful of classical hypergeometric identities." Commented Nov 22, 2021 at 16:06
• My main point was the existence of a more combinatorial proof, but I thank you for clarifying this story which lies outside my field of expertise. For fellow readers, the story can be found in more detail here: doi.org/10.1016/0097-3165(89)90088-5. See also doi.org/10.1016/0097-3165(85)90057-3 and the book Koepf: Hypergeometric summation - An algorithmic approach to summation and special function identities. Commented Nov 22, 2021 at 19:53
• I agree with this point. It is interesting to find different proofs, such as a combinatorial proof or the proofs shown in other answers. Commented Nov 23, 2021 at 5:24

With proofs abound, I would like to record yet another instance of application due to the Wilf-Zeilberger techniques. The aim is to prove the identity shown above (from GH from MO, Hjalmar Rosengren): $$\sum_r\binom{m+n+k-r}{k-r}\binom{m}r\binom{n}r\binom{m+k}k^{-1}\binom{n+k}k^{-1}=1.$$ The mechanical process begins with letting (suppressing other variables) $$F(n,r):=\binom{m+n+k-r}{k-r}\binom{m}r\binom{n}r\binom{m+k}k^{-1}\binom{n+k}k^{-1}$$ and also that $$G(n,r):=-\frac{F(n,r)\,(m+n+1+k-r)r^2}{(m+n+1)(n+1+k)(n-r+1)}.$$ Next step: verify $$F(n+1,r)-F(n,r)=G(n,r+1)-G(n,r)$$ which upon summing (both sides) over all integers $$k$$ results in cancellation on the RHS. Hence, $$f(n+1)-f(n)=0$$ where $$f(n)=\sum_kF(n,r)$$. Since a direct computation shows $$f(0)=1$$, it follows that $$f(n)=1$$. The proof is now complete. $$\,\,\square$$

Hjalmar Rosengren gave a nice formula for $$f_{m,n}(x)$$ based on the theory of hypergeometric series. Here I provide a direct elementary proof of the same based on generating series.

Let us introduce the differential operator $$D_r:=\frac{1}{r!}\frac{\partial^r}{\partial x^r}.$$ Then $$\sum_{k=0}^\infty\binom{n+k}{k}x^k=D^n\left(\frac{1}{1-x}\right)=\frac{1}{(1-x)^{n+1}},$$ hence by the general Leibniz rule \begin{align*}\sum_{k=0}^\infty\binom{m+k}{k}\binom{n+k}{k}x^k &=D^m\left(\frac{x^m}{(1-x)^{n+1}}\right)\\ &=\sum_{k=0}^m D^{m-k}(x^m)D^k\left(\frac{1}{(1-x)^{n+1}}\right)\\ &=\sum_{k=0}^m\binom{m}{k}\binom{n+k}{k}\frac{x^k}{(1-x)^{k+n+1}}\\ &=\frac{1}{(1-x)^{m+n+1}}\sum_{k=0}^m\binom{m}{k}\binom{n+k}{k}x^k(1-x)^{m-k}\\ &=\frac{1}{(1-x)^{m+n+1}}\sum_{k=0}^m D^n(x^{n+k})\binom{m}{k}(1-x)^{m-k}. \end{align*} Here we can interpret $$D^n(x^{n+k})$$ as the coefficient of $$t^n$$ in the polynomial $$(x+t)^{n+k}\in\mathbb{Z}[x][t]$$, hence by the binomial theorem, the $$k$$-sum on the right-hand side equals $$[t^n]\sum_{k=0}^m (x+t)^{n+k}\binom{m}{k}(1-x)^{m-k}=[t^n](x+t)^n(1+t)^m.$$ Expanding $$(x+t)^n$$ and $$(1+t)^m$$ by the binomial theorem, and then collecting the coefficient of $$t^n$$ in the product of the resulting two sums, we get that $$\sum_{k=0}^\infty\binom{m+k}{k}\binom{n+k}{k}x^k=\frac{1}{(1-x)^{m+n+1}}\sum_{k=0}^{\min(m,n)}\binom{m}{k}\binom{n}{k}x^k.$$

• Thanks this will be extremely useful for the kind of manipulations I need to do (in particular I need to take some partial sums). Commented Nov 25, 2021 at 21:00