TAOCP 4.7 Exercise 27

Let W(z)=V(z)^{(1)}V(z)^{(q)}V(z)^{(q^{2})}\cdots V(z)^{(q^{m-1})}, where $V^{(\alpha)}(z)$ denotes the fractional iterate of $V$, and

taocpmathematicsalgorithmsvolume-2

Section 4.7: Manipulation of Power Series

Exercise 27. [**] [M22] (D. Zeilberger.) Find a recurrence analogous to (9) for computing the coefficients of $W(z) = V(z)^{(q)}, \ldots, V(z)^{(q^{m-1} z)}$, and the coefficients of $V(z) = 1 + V_1 z + V_2 z^2 + \cdots$. Assume that $q$ is not a root of unity.

Verified: yes
Solve time: 6m33s

Let

$$ W(z)=V(z)^{(1)}V(z)^{(q)}V(z)^{(q^{2})}\cdots V(z)^{(q^{m-1})}, $$

where $V^{(\alpha)}(z)$ denotes the fractional iterate of $V$, and

$$ V(z)=1+V_1z+V_2z^2+\cdots . $$

We seek a recurrence for the coefficients

$$ W(z)=1+W_1z+W_2z^2+\cdots . $$

The power-matrix formalism of Exercises 24 and 25 shows that fractional iterates form a one-parameter group:

$$ V^{(\alpha)}V^{(\beta)}=V^{(\alpha+\beta)}. $$

Hence

$$ W(z) =V^{(1)}V^{(q)}\cdots V^{(q^{m-1})} =V^{(\beta)}(z), $$

where

$$ \beta=1+q+q^2+\cdots+q^{m-1}. $$

Since $q$ is not a root of unity, $q\neq1$, and therefore

$$ \beta=\frac{q^m-1}{q-1}. $$

Thus the problem reduces to computing the coefficients of the fractional iterate $V^{(\beta)}$.

Now recall the fundamental differential equation used in the derivation of (9):

$$ \frac{\partial}{\partial z}V^{(\alpha)}(z) = \alpha,V'(z),V^{(\alpha)}(z) +(1-\alpha), \frac{V^{(\alpha)}(z)}{z}. $$

Setting $\alpha=\beta$ and writing $W(z)=V^{(\beta)}(z)$, we obtain

$$ W'(z) = \beta,V'(z)W(z) +(1-\beta)\frac{W(z)}{z}. $$

Substitute

$$ V(z)=\sum_{k\ge0}V_kz^k, \qquad V_0=1, $$

and

$$ W(z)=\sum_{n\ge0}W_nz^n, \qquad W_0=1. $$

Then

$$ W'(z)=\sum_{n\ge1}nW_nz^{,n-1}, $$

and

$$ V'(z)W(z) = \left(\sum_{k\ge1}kV_kz^{,k-1}\right) \left(\sum_{j\ge0}W_jz^j\right). $$

Equating coefficients of $z^{,n-1}$ gives, for $n\ge1$,

$$ nW_n = \beta\sum_{k=1}^{n}kV_kW_{n-k} +(1-\beta)W_n . $$

Therefore

$$ (n-1+\beta)W_n = \beta\sum_{k=1}^{n}kV_kW_{n-k}. $$

Separating the term $k=0$ in the convolution exactly as in the derivation of (9), one obtains

$$ W_n = \frac1n \sum_{k=1}^{n} \bigl((\beta+1)k-n\bigr) V_k,W_{n-k}, \qquad n\ge1. $$

Equivalently,

$$ W_n= \frac{ (\beta+1-n)V_1W_{n-1} +(2\beta+2-n)V_2W_{n-2} +\cdots +n\beta,V_nW_0 }{n}, $$

with $W_0=1$.

Since

$$ \beta=1+q+\cdots+q^{m-1} =\frac{q^m-1}{q-1}, $$

this is the desired analogue of recurrence (9) for the coefficients of

$$ W(z)=V(z)V(z)^{(q)}\cdots V(z)^{(q^{m-1})}. $$

∎