Derive the identity $$ \sum_{k}\binom{tk+r}{k}\binom{tn-tk+s}{n-k} \frac{r}{tk+r}=\binom{tn+r+s}{n}\tag0{}$$

This question is from Aigner's A course in Enumeration.


A construction given prior to this problem is said to be useful in deriving the identity.

Namely, any generating function $F(z)=\sum_{n\geq 0}a_n z^n$ with $a_0=1, a_1\neq 0$, defines a polynomial sequence by $\exp(x\log F(z))=F(z)^x=\sum_{n\geq 0}p_{n}(x)z^n$ where $p_n(1)=a_n$ and $p_n(0)=[n=0]$. I showed that $p_n$ is a polynomial of degree $n$ and that $$ p_n(x+y)=\sum_{k=0}^np_{k}(x)p_{n-k}(y)\tag{1} $$ as well as $$ (x+y)\sum_{k=0}^nkp_{k}(x)p_{n-k}(y)=nxp_n(x+y).\tag{2} $$ My attempt

Equation (0) looked like a manifestation of the convolution in (1) with $p_n(x)=\binom{tn+x}{n}$. But I was unable to find an expression for $\sum_{n\geq 0 } \binom{tn+x}{n} z^n$ in closed form. It looks similar to $$ \sum_{n\geq 0}\binom{n+k}{n}z^n=\frac{1}{(1-z)^{k+1}} $$ but the $tn$ in the binomial coefficient is throwing me off.

Any help with an attempt using the context outlined above is preferred but other solutions are welcome as well.

  • $\begingroup$ For what it’s worth, Mathematica says (result extrapolated from small integer values of $t$) that $$\sum_{n\geq 0 } \binom{tn+x}{n} z^n=\,_{t}F_{t-1}(\frac{1+x}t,\frac{2+x}t,\dots\frac{t+x}t;\frac{1+x}{t-1},\frac{2+x}{t-1},\dots\frac{t+x}{t-1};z)$$, where $F$ is the generalized hypergeometric function. Don’t ask how to show this or even what it means... $\endgroup$ – Steve Kass Jun 13 '18 at 1:18
  • $\begingroup$ See the following posting for a reference to combinatoric proof of this identity: math.stackexchange.com/questions/2816467/… $\endgroup$ – Sangchul Lee Jun 13 '18 at 5:51

Here is a solution more in line with Aigner's hints. Much of this is lifted directly from Knuth's Convolution Polynomials, available on the arXiv.

You were trying to use $(1)$ with $p_n(x)=\binom{tn+x}{n}$, but it turns out the correct method is to use $(2)$ with $$p_n(x)=\binom{tn+x}{n}\frac{x}{x+tn}.$$The result is $$ (x+y)\sum k\binom{tk+x}{k}\frac{x}{x+tk}\binom{t(n-k)+y}{n-k}\frac{y}{y+t(n-k)}=nx\binom{tn+x+y}{n}\frac{x+y}{x+y+tn} $$ Canceling the $x$ and $x+y$, and applying the absorption identities $\binom{tn+x+y}{n}=\frac{tn+x+y}{n}\binom{tn+x+y-1}{n-1}$, and $\binom{tk+x}{k}=\frac{tk+x}{k}\binom{tk+x-1}{k-1}$, we get $$ \sum_k \binom{tk+x-1}{k-1}\binom{t(n-k)+y}{n-k}\frac{y}{y+t(n-k)}=\binom{tn+x+y-1}{n-1} $$ Finally, the result follows by replacing $n$ with $n+1$, reversing the order of summation ($k\leftarrow n+1-k $), and replacing $x$ with $x-t+1$.

Of course, you still need to find a function $F(z)$ for which $$F(z)^x=\sum_{n\ge0}p_n(x)z^n=\sum_{n\ge0}\binom{tn+x}{n}\frac{x}{tn+x}z^n\tag{*}.$$ It turns out that the answer is $$F(z)=\sum_{n\ge0}\binom{tn+1}{n}\frac{z^n}{tn+1}\tag{**}$$ This is a function which satisfies $$ F(z) = 1+zF(z)^t\tag{***} $$ You can use take (***) as a definition of $F$, and recover (**) via Lagrange inversion. Knuth gives an interesting combinatorial proof of how (**) implies (*) in Concrete Mathematics, section 7.5. I think there should be a way to show (***) implies (*) via Lagrange inversion, but so far I have been unsuccessful.

  • 1
    $\begingroup$ I have added the Lagrange inversion computation. $\endgroup$ – Marko Riedel Jun 16 '18 at 0:39

We see that our identity is in fact

$$\sum_{k=0}^n {tk+r\choose k} {tn-tk+s\choose n-k} - \sum_{k=0}^n {tk+r\choose k} {tn-tk+s\choose n-k} \frac{tk}{tk+r} \\ = {tn+r+s\choose n}.$$

While it would be preferable to solve this using formal power series only it appears we need complex variables for this one. With integers $t,r,s \ge 1$ and starting with the first sum we introduce

$${tk+r\choose k} = \frac{1}{2\pi i} \int_{|w|=\gamma} \frac{1}{w^{k+1}} (1+w)^{tk+r} \; dw$$


$${tn-tk+s\choose n-k} = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n-k+1}} (1+z)^{tn-tk+s} \; dz.$$

This last integral vanishes when $k\gt n$ so we may extend the sum to infinity, getting

$$\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{tn+s}}{z^{n+1}} \frac{1}{2\pi i} \int_{|w|=\gamma} \frac{(1+w)^{r}}{w} \sum_{k\ge 0} z^k (1+z)^{-tk} \frac{1}{w^k} (1+w)^{tk} \; dw \; dz.$$

Now with $\epsilon$ and $\gamma$ small in a neighborhood of the origin we get that for this to converge we must have $\epsilon/(1-\epsilon)^t \lt \gamma/(1+\gamma)^t.$ We shall see that we may solve this with an additional constraint, namely that $\gamma \gt\epsilon.$ Doing the summation we find

$$\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{tn+s}}{z^{n+1}} \frac{1}{2\pi i} \int_{|w|=\gamma} \frac{(1+w)^{r}}{w} \frac{1}{1-z(1+w)^t/w/(1+z)^t} \; dw \; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{tn+s}}{z^{n+1}} \frac{1}{2\pi i} \int_{|w|=\gamma} (1+w)^{r} \frac{1}{w-z(1+w)^t/(1+z)^t} \; dw \; dz.$$

The pole at $w=0$ has been canceled. There is a pole at $w=z$ however and with the chosen parameters it is inside the contour. We get for the residue

$$\left.(1+w)^r \frac{1}{1-tz(1+w)^{t-1}/(1+z)^t}\right|_{w=z} = (1+z)^r \frac{1}{1-tz/(1+z)}$$

The derivative would have vanished if the pole had not been simple. Substituting into the outer integral we get

$$\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{tn+r+s+1}}{z^{n+1}} \frac{1}{1-(t-1)z} \; dz.$$

Continuing with the second sum we obtain

$$\sum_{k=1}^n {tk+r\choose k} {tn-tk+s\choose n-k} \frac{tk}{tk+r} = t \sum_{k=1}^n {tk+r-1\choose k-1} {tn-tk+s\choose n-k} \\ = t \sum_{k=0}^{n-1} {tk+t+r-1\choose k} {t(n-1)-tk+s\choose (n-1)-k}.$$

We can recycle the earlier computation and find

$$\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{t(n-1)+t+r-1+s+1}}{z^{n}} \frac{t}{1-(t-1)z} \; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{tn+r+s}}{z^{n+1}} \frac{tz}{1-(t-1)z} \; dz.$$

Subtracting the two the result is

$$\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{tn+r+s}}{z^{n+1}} \frac{(1+z)-tz}{1-(t-1)z} \; dz = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{tn+r+s}}{z^{n+1}} \; dz.$$

This evaluates to

$${tn+r+s\choose n}$$

by inspection and we have proved the theorem.

To show that the pole at $w=z$ is the only one inside the contour apply Rouche's theorem to

$$h(w) = w(1+z)^t - z(1+w)^t$$

with $f(w) = w (1+z)^t$ and $g(w) = z (1+w)^t.$ We need $|g(w)| < |f(w)|$ on $|w|=\gamma$ and since $f(w)$ has only one root there so does $h(w)$, which must be $w=z.$ We thus require

$$|g(w)| \le |z| (1+\gamma)^t \lt \gamma |1+z|^t = |f(w)|.$$

Now $\gamma/(1+\gamma)^t$ starts at zero and is increasing since $(1+\gamma-\gamma t)/(1+\gamma)^{t+1}$ is positive for $\gamma \lt 1/(t-1)$ with a local maximum there. Since $|z|/|1+z|^t \le \epsilon / (1-\epsilon)^t$ we may choose $\epsilon$ for this to take on a value from the range of $\gamma/(1+\gamma)^t$ on $[0, 1/(t-1)].$ Instantiating $\gamma$ to the right of this point yields a value $\gt \epsilon$ that fulfils the requirements of the theorem. Here we have used that $\epsilon/(1+\epsilon)^t \lt \epsilon/(1-\epsilon)^t \lt \gamma/(1+\gamma)^t$ by construction. No need for Rouche when $t=1.$


This answer is based upon the Lagrange inversion theorem. Here we use a variant which is stated as G.6 in Lagrange Inversion: when and how by D. Merlini, R. Sprugnoli and M.C. Verri. It goes as follows:

Assume $w=w(z)$ is a formal power series which is implicitly given as $w=z\phi(w)$ with $\phi(0)\ne 0$. Then for any formal power series $F$ we have \begin{align*} \sum_{k=0}^\infty\left([u^k]F(u)\phi(u)^k\right)w(z)^k=\left.\frac{F(w)}{1-z\phi^\prime (w)}\right|_{w=z\phi(w)}\tag{1} \end{align*} where $[u^k]$ is the coefficient of operator denoting the coefficient of $u^k$ in a series.

We start with the left-hand side of OPs identity, put it into a power series $w=w(z)$ and observe that this is the Cauchy-product of two power series. \begin{align*} \sum_{k=0}^\infty&\binom{tk+r}{k}\binom{tn-tk+s}{n-k}\frac{r}{tk+r}w^k\\ &=\left(\sum_{k=0}^\infty \binom{tk+r}{k}\frac{r}{tk+r} w^k\right)\left(\sum_{k=0}^\infty \binom{tk+s}{k} w^k\right)\tag{2} \end{align*}

We derive closed expressions of the formal power series in (2) from which the claim easily follows.

We start with the right-hand power series in (2) and obtain \begin{align*} \color{blue}{\sum_{k=0}^\infty\binom{tk+s}{k}w(z)^k}&=\sum_{k=0}^\infty[u^k](1+u)^{tk+s}w(z)^k\tag{3}\\ &=\left.\frac{(1+w)^s}{1-zt(1+w)^{t-1}}\right|_{w=z(1+w)^t}\tag{4}\\ &=\left.\frac{(1+w)^s}{1-\frac{w}{(1+w)^t}t(1+w)^{t-1}}\right|_{w=z(1+w)^t}\tag{5}\\ &\,\,\color{blue}{=\left.\frac{(1+w)^s}{1-(t-1)w}\right|_{w=z(1+w)^t}}\tag{6} \end{align*}


  • In (3) we write the binomial coefficient using the coefficient of operator and observe that we can apply (1) with $\phi(w)=(1+w)^t$.

  • In (4) we use the Lagrange inversion theorem (1) by setting $F(w)=(1+w)^s$.

  • In (5) we do the substitution $z=\frac{w}{(1+w)^t}$.

  • In (6) we make some final simplification.

Similarly we get a closed expression for the left-hand power series in (2). We obtain \begin{align*} \color{blue}{\sum_{k=0}^\infty}&\color{blue}{\binom{tk+r}{k}\frac{r}{tk+r}w(z)^k}\\ &=\sum_{k=0}^\infty\left(\binom{tk+r}{k}-t\binom{tk+r-1}{k-1}\right)w(z)^k\tag{7}\\ &=\sum_{k=0}^\infty\left([u^k](1+u)^{tk+r}-t[u^{k-1}](1+u)^{tk+r-1}\right)w(z)^k\tag{8}\\ &=\sum_{k=0}^\infty\left([u^k](1-(t-1)u)(1+u)^{tk+r-1}\right)w(z)^k\tag{9}\\ &=\left.\frac{(1-(t-1)w)(1+w)^{r-1}}{1-zt(1+w)^{t-1}}\right|_{w=z(1+w)^t}\tag{10}\\ &=\left.\frac{(1-(t-1)w)(1+w)^{r-1}}{1-\frac{w}{(1+w)^t}t(1+w)^{t-1}}\right|_{w=z(1+w)^t}\tag{11}\\ &\,\,\color{blue}{=\left.(1+w)^r\right|_{w=z(1+w)^t}}\tag{12} \end{align*}


  • In (7) we write $\frac{r}{tk+r}=1-\frac{tk}{tk+r}$ and apply the binomial identity $\binom{p}{q}=\frac{p}{q}\binom{p-1}{q-1}$.

  • In (8) we apply the coefficient of operator twice.

  • In (9) we use the linearity of the coefficient of operator and apply the rule $[u^p]u^qA(u)=[u^{p-q}]A(u)$.

  • In (10) work similarly as above with $\phi(w)=(1+w)^t$ and $F(w)=(1-(t-1)w)(1-w)^{r-1}$.

  • In (11) we do the substitution $z=\frac{w}{(1+w)^t}$.

  • In (12) we make some final simplification.

Putting the closed forms (6) and (12) together we obtain \begin{align*} \sum_{k=0}^\infty&\color{blue}{\binom{tk+r}{k}\binom{t(n-k)+s}{n-k}\frac{r}{tk+r}}w(z)^k\\ &=\left.\frac{(1+w)^{r+s}}{1-(t-1)w}\right|_{w=z(1+w)^t}\\ &=\sum_{k=0}^\infty\color{blue}{\binom{tk+r+s}{k}}w(z)^k \end{align*} where the last step follows due to (6) and the claim follows.

Note: This derivation can be found in a slightly different manner in the paper by D. Merlini et al. referenced above.


Working with the query at the end of the accepted answer we can show that with $x,t$ positive integers and

$$F(z) = 1 + z F(z)^t$$


$$F(z)^x = \sum_{n\ge 0} {tn+x\choose n} \frac{x}{tn+x} z^n$$

using the Lagrange-Buermann formula.

We put $w = F(z)-1$ so that $z=w/(w+1)^t$ and

$$[z^n] F(z)^x = \frac{1}{n} [w^{n-1}] x (w+1)^{x-1} (w+1)^{tn} \\ = \frac{x}{n} [w^{n-1}] (w+1)^{tn+x-1} = \frac{x}{n} {tn+x-1\choose n-1} \\ = \frac{x}{tn+x} {tn+x\choose n}.$$

as claimed. Here we have used $H(w) = (w+1)^x$ in the notation of the Wikipedia entry.


First, using vandermonde, we get:

$$\binom{tn-tk+s}{n-k} = \sum_{j=k}^n\binom{tn + s + r}{n-j}\binom{-r-tk}{j-k}$$

LHS = $$\sum_{k=0}^n\frac{r}{tk+r}\binom{tk+r}{k}\binom{tn-tk+s}{n-k}$$

$$= \sum_{k=0}^n\frac{r}{tk+r}\binom{tk+r}{k}\sum_{j=k}^n\binom{tn + s + r}{n-j}\binom{-r-tk}{j-k}$$

$$= \sum_{j=0}^n\binom{tn + s + r}{n-j}\sum_{k=0}^j\frac{r}{tk+r}\binom{tk+r}{k}\binom{-r-tk}{j-k}$$

For the term $\binom{-r-tk}{j-k}$, we can negate the upper index using: $\binom{r}{k} = (-1)^k \binom{k-r-1}{k}$

LHS = $$\sum_{j=0}^n\binom{tn + s + r}{n-j}\sum_{k=0}^j\frac{(-1)^{j-k}r}{tk+r}\binom{tk+r}{k}\binom{j-k + r+tk-1}{j-k}$$

Now $$\frac{r}{tk+r}\binom{tk+r}{k}\binom{j-k + r+tk-1}{j-k} = \frac{r}{tk+r}\frac{(tk+r)!}{(tk+r-k)!k!}\frac{(j-k+r+tk-1)!}{(tk+r-1)!(j-k)!}$$

Cancelling out the $(tk+r)!$ from numerator and denominator, we get:


Multiplying num and den by $(j-k+r+tk)$, we get

$$\frac{r}{(j-k+r+tk)}\binom{j}{k} \binom{j-k+r+tk}{j}$$

Plugging this back into LHS, we get:

LHS = $$\sum_{j=0}^n\binom{tn + s + r}{n-j}\sum_{k=0}^j\frac{(-1)^{j-k}r}{(j-k+r+tk)}\binom{j}{k} \binom{j-k+r+tk}{j}$$

Now comes the leap of faith:

for $j>0$, the inner sum becomes $0$. [proof needed]

And so LHS = $\binom{tn + s + r}{n}$


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.