Proof of a Combinatorial Abel Identity Question

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.
Context
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.
 A: 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$$
and
$${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.$
A: 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.
A: 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*}

Comment:


*

*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*}

Comment:


*

*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.
A: 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$$
that
$$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.
A: 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:
$$\frac{r}{1}\frac{(j-k+r+tk-1)!}{(tk+r-k)!j!}\frac{j!}{k!(j-k)!}$$
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}$
