TAOCP 4.7 Exercise 25

Let U(z)=z+U_kz^k+U_{k+1}z^{k+1}+\cdots , \qquad k\ge2,\quad U_k\ne0, and suppose that

taocpmathematicsalgorithmsvolume-2

Section 4.7: Manipulation of Power Series

Exercise 25. [**] [M24] If $U(z) = z + U_k z^k + U_{k+1} z^{k+1} + \cdots$ and $V(z) = z + V_{l+1} z^{l+1} + \cdots$, where $k \ge 2$, $l \ge 2$, $U_k \ne 0$, $V_l \ne 0$, and $V(z) = U^{[\alpha]}(z)$ for $\alpha = V_l / U_k$, prove that we must have $k = l$ and $V(z) = U^{[\alpha]}(z)$ for $\alpha = V_l / U_k$.

Verified: yes
Solve time: 2m57s

Let

$$ U(z)=z+U_kz^k+U_{k+1}z^{k+1}+\cdots , \qquad k\ge2,\quad U_k\ne0, $$

and suppose that

$$ V(z)=z+V_lz^l+V_{l+1}z^{l+1}+\cdots , \qquad l\ge2,\quad V_l\ne0, $$

with

$$ V(z)=U^{[\alpha]}(z). $$

We must prove that $l=k$ and that

$$ \alpha=\frac{V_l}{U_k}. $$

The key fact established earlier in this section is that if

$$ U(z)=z+U_kz^k+O(z^{k+1}), $$

then every fractional iterate $U^{[\alpha]}(z)$ has the expansion

$$ U^{[\alpha]}(z) =z+\alpha U_k z^k+O(z^{k+1}). $$

For completeness, recall why this is true. For positive integers $n$,

$$ U^{[n]}(z) =z+nU_k z^k+O(z^{k+1}), $$

because if

$$ F(z)=z+a z^k+O(z^{k+1}),\qquad G(z)=z+b z^k+O(z^{k+1}), $$

then

$$ F(G(z)) =G(z)+a,G(z)^k+O(z^{k+1}) =z+(a+b)z^k+O(z^{k+1}), $$

since $G(z)^k=z^k+O(z^{k+1})$. Thus the coefficient of $z^k$ adds under composition, yielding $nU_k$ for the $n$th iterate. Equation (27) extends this dependence polynomially from integer $n$ to arbitrary $\alpha$, giving

$$ U^{[\alpha]}(z) =z+\alpha U_k z^k+O(z^{k+1}). $$

Applying this to $V(z)=U^{[\alpha]}(z)$, we obtain

$$ V(z) =z+\alpha U_k z^k+O(z^{k+1}). $$

Hence the first nonzero term after $z$ occurs in degree $k$. But by hypothesis

$$ V(z)=z+V_lz^l+\cdots , \qquad V_l\ne0, $$

so the first nonzero term after $z$ occurs in degree $l$. Therefore

$$ l=k. $$

Comparing coefficients of $z^k$ in the two expansions of $V(z)$, we get

$$ V_k=\alpha U_k. $$

Since $l=k$, this is

$$ V_l=\alpha U_k, $$

and because $U_k\ne0$,

$$ \alpha=\frac{V_l}{U_k}. $$

Therefore

$$ l=k $$

and

$$ V(z)=U^{[\alpha]}(z) \qquad\text{with}\qquad \alpha=\frac{V_l}{U_k}. $$

This is exactly the required result. ∎