Proof of a Combinatorial Abel Identity

Question

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.

Answer 1

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.

Answer 2

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

Answer 3

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

Answer 4

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.

Answer 5

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.