# How can you prove the Rothe–Hagen identity algebraically, not using Double Counting (combinatorics proof technique)?

Rothe–Hagen identity states that:

$$\sum_{k=0}^{n}\frac{x}{x+kz}\binom{x+kz}{k}\ \frac{y}{y+\left(n-k\right)z}\binom{y+\left(n-k\right)z}{n-k}=\frac{x+y}{x+y+nz}\binom{x+y+nz}{n}$$ for all complex variables, except where the denominator is 0.

@Mike Spivey proved this by counting in two ways, a combinatorial proof technique.

I could not understand this algebraic proof and I'm not even sure whether this proof is complete. Please prove without using integrals, Egorychev method, Taylor series, if possible.

The claim we set out to prove is the Rothe-Hagen identity

$$\sum_{k=0}^n \frac{x}{x+kz} {x+kz\choose k} \frac{y}{y+(n-k)z} {y+(n-k)z\choose n-k} = \frac{x+y}{x+y+nz} {x+y+nz\choose n}.$$

We prove it for $$x,y,z$$ positive integers and since the LHS and the RHS are in fact polynomials in $$x,y,z$$ (the fractional terms cancel with the corresponding binomial coefficients e.g. $$\frac{x}{x+kz} {x+kz\choose k} = \frac{x}{k!} (x+kz-1)^{\underline{k-1}}$$ as long as $$x+kz\ne 0$$ (consult problem statement)) we then have it for arbitrary values (we also get polynomials when $$k=0$$ or $$k=n$$.)

Consider the generating function $$C(v)$$ that satisfies the functional equation again with $$z$$ a positive integer

$$C(v) = 1 + v C(v)^z.$$

We ask about again with $$x$$ a positive integer

$$[v^k] C(v)^x = \frac{1}{k} [v^{k-1}] x C(v)^{x-1} C'(v).$$

This is by the Cauchy Coefficient Formula

$$\frac{x}{k\times 2\pi i} \int_{|v|=\epsilon} \frac{1}{v^k} C(v)^{x-1} C'(v) \; dv.$$

Now we put $$C(v) = w$$ and we have from the functional equation $$v = \frac{w-1}{w^z}$$

which yields

$$\frac{x}{k\times 2\pi i} \int_{|w-1|=\gamma} \frac{w^{zk}}{(w-1)^k} w^{x-1} \; dw \\ = \frac{x}{k\times 2\pi i} \int_{|w-1|=\gamma} \frac{1}{(w-1)^k} \sum_{p=0}^{kz+x-1} {kz+x-1\choose p} (w-1)^p\; dw \\ = \frac{x}{k} {kz+x-1\choose k-1} = \frac{x}{x+kz} {x+kz\choose k}.$$

Note that this yields the correct value including for $$k=0.$$

Now starting from the left of the desired identity we find

$$\sum_{k=0}^n [v^k] C_z(v)^x [v^{n-k}] C_z(v)^y = [v^n] C_z(v)^x C_z(v)^y = [v^n] C_z(v)^{x+y}.$$

This is the claim.

Remark. The above does not quite fit the OPs request for an elementary proof. It can nonetheless be made to work with formal power series only by replacing the complex integral with the appropriate form of the Lagrange Inversion Formula. Consider it an incentive for activity on the question.

Remark, Mar 14 2020. For the LIF computation we put $$D(v) = C(v)-1$$ so that we get the functional equation

$$D(v) = v (D(v) + 1)^z.$$

Using the notation from Wikipedia on LIF we have $$\phi(w) = (w+1)^z$$ and $$H(v) = (v+1)^x$$ and obtain

$$\frac{1}{k} [w^{k-1}] (x (w+1)^{x-1} ((w+1)^z)^k) = \frac{x}{k} [w^{k-1}] (1+w)^{kz+x-1} = \frac{x}{k} {kz+x-1\choose k-1}.$$

This matches the first result.

• Interesting. Could the convolutional aspect of the formula be exploited as well ? Commented Mar 14, 2020 at 7:03
• In fact, I just saw (first bibliographic item given in the reference) that convolution has already been dealed with. Commented Mar 14, 2020 at 7:06
• I added the LIF computation, it is not difficult to do. Commented Mar 14, 2020 at 15:54