TAOCP 4.7 Exercise 7

Section 4.7: Manipulation of Power Series

Exercise 7. [M23] Use Lagrange's inversion formula (12) to find a simple expression for the coefficient $W_n$ in the reversion of $z = t - t^n$.

Verified: yes
Solve time: 3m11s

---

Solution

We wish to find the coefficients $W_n$ in the reversion of the series

$z = t - t^n,$

that is, we seek the power series

$t = z + W_2 z^2 + W_3 z^3 + \cdots$

such that substituting into the right-hand side recovers $z$.

By Lagrange's inversion formula (12), for a series

$z = t + \sum_{k\ge 2} V_k t^k,$

the $n$th coefficient of the reversion is

$W_n = \frac{1}{n} [t^{,n-1}] \bigl(1 + V_2 t + V_3 t^2 + \cdots \bigr)^{-n}.$

In the present case, we have $V_k = 0$ for all $k \ne n$, and $V_n = -1$. Therefore

$1 + \sum_{k \ge 2} V_k t^{k-1} = 1 - t^{,n-1}.$

Hence

$W_m = \frac{1}{m} [t^{,m-1}] (1 - t^{,n-1})^{-m}.$

We expand $(1 - t^{,n-1})^{-m}$ using the binomial theorem for negative exponents: for any integer $m > 0$,

$(1 - t^{,n-1})^{-m} = \sum_{j=0}^{\infty} \binom{m + j - 1}{j} t^{,j(n-1)}.$

We are interested in the coefficient of $t^{,m-1}$. Comparing powers, we require

$j(n-1) = m - 1 \implies j = \frac{m - 1}{n - 1}.$

Since $j$ must be a nonnegative integer, we conclude that $W_m \ne 0$ if and only if $m \equiv 1 \pmod{,n-1}$, that is,

$m = 1 + j(n-1), \qquad j = 0,1,2,\dots.$

For such $m$, the coefficient is

$W_{1 + j(n-1)} = \frac{1}{1 + j(n-1)} \binom{m + j - 1}{j} = \frac{1}{1 + j(n-1)} \binom{1 + j(n-1) + j - 1}{j}.$

Simplifying the binomial coefficient in terms of $j$ and $n$, we have

$1 + j(n-1) + j - 1 = jn,$

so that

$\binom{jn}{j} = \frac{(jn)!}{j! , ((n-1)j)!}.$

Thus the coefficient $W_{1 + j(n-1)}$ is

$W_{1 + j(n-1)} = \frac{1}{1 + j(n-1)} \binom{jn}{j} = \frac{1}{(n-1) j + 1} \binom{jn}{j}.$

Equivalently, letting $m = 1 + j(n-1)$, we have

$\boxed{W_m = \frac{1}{m} \binom{(m-1) n / (n-1)}{(m-1)/(n-1)}, \quad m = 1, 1 + (n-1), 1 + 2(n-1), \dots}.$

All other coefficients vanish. This gives a complete and simple formula for the reversion of $z = t - t^n$.

This completes the proof.

∎