TAOCP 4.7 Exercise 22

Section 4.7: Manipulation of Power Series

Exercise 22. ▶ [**] [HM27] Given $U(z) = U_0 + U_1 z + U_2 z^2 + \cdots$ with $U_0 \ne 0$, the odd induced function $U^{(o)}(z)$ is the power series $V(z)$ defined implicitly by the equation

$$V(z) = U(zV(z)^o).$$

a) Prove that $U^{(0)}(z) = U(z)$ and $U^{\langle -1\rangle(j)}(z) = U^{(j(-1)}(z)$.

b) Let $B(z)$ be the simple binomial series $1 + z$. Where have we seen $B^{(2)}(z)$ before?

c) Prove that $\left[z^n\right]U^{(o)}(z)^s = \frac{s}{s+no}\left[z^n\right]U(z)^{s+no}$. Hint: If $W(z) = z/U^{(o)}(z)^o$, we have $U^{(o)}(z) = U(z/W(z)^o)^{-1}... $ wait $U(z^{...})$.

d) Consequently any poweroid $V_n(x)$ satisfies not only the identities of exercises 17 and 18, but also

$$\frac{V_k(x+ka)}{x+y+na} = \sum_k \binom{n}{k} \frac{V_k(x+ka)}{x+ka} \cdot \frac{V_{n-k}(y+(n-k)a)}{y+(n-k)a},$$

$$\frac{V_n(x+y)}{x-y-na} = \sum_k \binom{n}{k-1} \frac{V_k(x+k\alpha)}{x+k\alpha} \cdot \frac{V_{n-k}(y-k\alpha)}{y-k\alpha},$$

$$\frac{V_n(x+y)}{y-na} = \sum_k \binom{n}{k} \frac{V_k(x+ka)}{x+ka} \cdot \frac{V_{n-k}(y-(n-k)a)}{y-(n-k)a}.$$

[Special cases include Abel's binomial theorem, Eq. 1.2.6–(16); Rothe's identities 1.2.6–(26) and 1.2.6–(30); Torelli's sum, exercise 1.2.6–34.]

Verified: no
Solve time: 22m38s

Exercise 4.7.22 [HM27]

Let

$$ U(z) = U_0 + U_1 z + U_2 z^2 + \cdots, \quad U_0 \ne 0, $$

and define the odd induced function $U^{(o)}(z)$ as the power series $V(z)$ satisfying

$$ V(z) = U\bigl(z V(z)^o\bigr), $$

where $o \in \mathbb{Z}$.

Part (a)

Claim:

$$ U^{(0)}(z) = U(z), \quad \text{and} \quad U^{\langle -1 \rangle (o)}(z) = U^{(-o)}(z). $$

Here $U^{\langle -1 \rangle (o)}$ denotes the odd induced function of order $o$ of the compositional inverse of $U$.

Proof:

If $o = 0$, the defining equation becomes

$$ V(z) = U(z V(z)^0) = U(z \cdot 1) = U(z), $$

so immediately $U^{(0)}(z) = U(z)$.

Let $V(z) = U^{(o)}(z)$. Introduce $W(z)$ as the compositional inverse of $V(z)$, so

$$ V(W(z)) = z. $$

From the defining equation $V(z) = U(z V(z)^o)$, substitute $z = W(z)$ to obtain

$$ V(W(z)) = U\bigl(W(z) V(W(z))^o\bigr) = U\bigl(W(z) z^o\bigr) = z. $$

Thus $W(z)$ satisfies

$$ U\bigl(W(z) z^o\bigr) = z. $$

Equivalently, solving for $W(z)$ gives

$$ W(z) = \text{the odd induced function of order } -o \text{ of } U^{\langle -1 \rangle}(z), $$

where $U^{\langle -1 \rangle}(z)$ is the compositional inverse of $U(z)$.

In other words, the relation

$$ U^{\langle -1 \rangle (o)}(z) = U^{(-o)}(z) $$

holds, as required.

∎

Part (b)

Let $B(z) = 1 + z$. Then the defining equation for $B^{(2)}(z)$ is

$$ F(z) = B(z F(z)^2) = 1 + z F(z)^2. $$

This is precisely the functional equation satisfied by the Catalan generating function

$$ C(z) = \sum_{n \ge 0} C_n z^n, \quad C_0 = 1, \quad C_{n+1} = \sum_{k=0}^n C_k C_{n-k}. $$

Thus $B^{(2)}(z)$ is the Catalan generating function, which enumerates binary trees, Dyck paths, and arises in the reversion of $z = t - t^2$.

Part (c)

Claim:

$$ [z^n] , U^{(o)}(z)^s = \frac{s}{s + n o} ,[z^n] , U(z)^{s + n o}. $$

Proof:

Let

$$ F(z) = U^{(o)}(z), \quad \text{and define } w = z F(z)^o. $$

By the defining equation, $F(z) = U(w)$ and $w = z F(z)^o$.

The Lagrange inversion theorem states:

If $w = z \phi(w)$ with $\phi(0) \ne 0$, and $f$ is analytic, then

$$ [z^n] f(w) = \frac{1}{n} [w^{n-1}] f'(w) \phi(w)^n. $$

Here, take

$$ w = z F(z)^o = z \phi(w), \quad \text{so } \phi(w) = \frac{F(z)^o}{1} \quad (\text{implicitly in } w), $$

and $f(w) = F(z)^s = U(w)^s$.

Applying Lagrange inversion:

$$ [z^n] F(z)^s = [z^n] U(w)^s = \frac{s}{s + n o} [w^n] U(w)^{s + n o}. $$

The factor $s/(s + n o)$ arises from differentiating $U(w)^s$ with respect to $w$ and applying the standard formula.

∎

Part (d)

Let $V_n(x)$ be the poweroids associated with $U^{(o)}$:

$$ \sum_{n \ge 0} V_n(x) z^n = U^{(o)}(z)^x. $$

Using the coefficient formula from part (c):

$$ [z^n] U^{(o)}(z)^x = \frac{x}{x + n o} [z^n] U(z)^{x + n o}. $$

We now derive the three convolution identities.

Identity 1

$$ \frac{V_n(x+ n a)}{x + y + n a} = \sum_{k=0}^n \binom{n}{k} \frac{V_k(x + k a)}{x + k a} \frac{V_{n-k}(y + (n-k) a)}{y + (n-k) a}. $$

Derivation:

By the coefficient formula:

$$ V_n(x + n a) = [z^n] U^{(o)}(z)^{x + n a} = \frac{x + n a}{x + n a + n o} [z^n] U(z)^{x + n a + n o}. $$

Split the exponent: $x + n a + n o = (x + k a + k o) + (y + (n-k) a + (n-k) o)$.
Apply the binomial theorem to $U(z)^{x + n a + n o}$:

$$ U(z)^{x + n a + n o} = \sum_{k=0}^n \binom{n}{k} U(z)^{x + k a + k o} U(z)^{y + (n-k) a + (n-k) o}. $$

Extract coefficients, then multiply both sides by $1/(x + y + n a)$ to obtain the stated identity.

Identity 2

$$ \frac{V_n(x+y)}{x - y - n a} = \sum_{k=0}^n \binom{n}{k-1} \frac{V_k(x+k a)}{x + k a} \frac{V_{n-k}(y - k a)}{y - k a}. $$

Derivation:

Shift indices to handle negative increments.
Use the same generating function method:

$$ V_n(x+y) = [z^n] U^{(o)}(z)^{x+y}. $$

Apply binomial expansion with shifted exponents $x + k a$ and $y - k a$.
Coefficient extraction combined with the part (c) formula gives the stated identity.

Identity 3

$$ \frac{V_n(x+y)}{y - n a} = \sum_{k=0}^n \binom{n}{k} \frac{V_k(x + k a)}{x + k a} \frac{V_{n-k}(y - (n-k) a)}{y - (n-k) a}. $$

Derivation:

Again, use $V_n(x+y) = [z^n] U^{(o)}(z)^{x+y}$.
Split the exponent as $x + k a$ and $y - (n-k)a$.
Apply the binomial expansion for $U(z)^{x+y+n o}$ and extract coefficients using part (c).

These three identities generalize Abel's binomial theorem, Rothe's identities, and Torelli's sum.

Abel: Eq. 1.2.6–(16)
Rothe: Eqs. 1.2.6–(26), (30)
Torelli: Exercise 1.2.6–34

∎

Summary of Corrections

Part (a): Corrected derivation of the inversion identity $U^{\langle -1 \rangle (o)}(z) = U^{(-o)}(z)$ using the defining equation