TAOCP 4.7: Manipulation of Power Series
Section 4.7 exercises: 26/28 solved.
Section 4.7. Manipulation of Power Series
Exercises from TAOCP Volume 2 Section 4.7: 26/28 solved.
| # | Rating | Category | Status | Time |
|---|---|---|---|---|
| 1 | [M10] | math-simple | verified | 1m53s |
| 2 | [20] | medium | verified | 2m41s |
| 3 | [M15] | math-simple | verified | 1m44s |
| 4 | ▶ [HM23] | hm-medium | verified | 1m46s |
| 5 | [M00] | math-immediate | verified | 2m48s |
| 6 | [M21] | math-medium | verified | 4m15s |
| 7 | [M23] | math-medium | verified | 3m11s |
| 8 | ▶ [M25] | math-medium | verified | 19m12s |
| 9 | [11] | simple | - | - |
| 10 | [M20] | math-medium | - | - |
| 11 | ▶ [M25] | math-medium | verified | 6m09s |
| 12 | [M20] | math-medium | verified | 4m38s |
| 13 | [M27] | math-hard | verified | 11m50s |
| 14 | ▶ [HM30] | hm-hard | verified | 6m57s |
| 15 | [HM30] | hm-hard | verified | 4m44s |
| 16 | [HM21] | hm-medium | solved | 2m19s |
| 17 | ▶ [M20] | math-medium | solved | 4m |
| 18 | [**] | verified | 1m36s | |
| 19 | [**] | verified | 8m05s | |
| 20 | [**] | solved | 3m03s | |
| 21 | ▶ [**] | solved | 2m17s | |
| 22 | ▶ [**] | solved | 22m38s | |
| 23 | [**] | verified | 13m07s | |
| 24 | [**] | verified | 5m59s | |
| 25 | [**] | verified | 2m57s | |
| 26 | [**] | solved | 9m48s | |
| 27 | [**] | verified | 6m33s | |
| 28 | ▶ [**] | verified | 3m54s |
TAOCP 4.7 Exercise 1
If $V_0 = 0$, let $m$ be the smallest index such that $V_m \ne 0$.
TAOCP 4.7 Exercise 2
Let $U(z) = U_0 + U_1 z + U_2 z^2 + \cdots, \qquad V(z) = V_0 + V_1 z + V_2 z^2 + \cdots$ be power series with integer coefficients, and suppose $V_0 \ne 0$.
TAOCP 4.7 Exercise 3
We examine formula (9) from Section 4.
TAOCP 4.7 Exercise 4
Let $W(z)=e^{U(z)}, \qquad U(z)=U_1z+U_2z^2+\cdots,$ where $U_0=0$.
TAOCP 4.7 Exercise 5
If a power series is reverted twice, the second reversion undoes the first.
TAOCP 4.7 Exercise 6
Let $W(z)=\frac1{V(z)}, \qquad V_0\ne0.$ Then $W(z)$ is the root of $f(x)=x^{-1}-V(z).$ Newton's method for solving $f(x)=0$ is $x_{m+1}=x_m-\frac{f(x_m)}{f'(x_m)}.$
TAOCP 4.7 Exercise 7
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 s...
TAOCP 4.7 Exercise 8
Let z=V(t)=V_1t+V_2t^2+V_3t^3+\cdots,\qquad V_1\neq0, and let
TAOCP 4.7 Exercise 11
We are asked to compute the first $N$ coefficients of the composition of two formal power series U(z) = U_0 + U_1 z + U_2 z^2 + \cdots, \qquad V(z) = V_1 z + V_2 z^2 + V_3 z^3 + \cdots,
TAOCP 4.7 Exercise 12
Let with $v_n\ne0$.
TAOCP 4.7 Exercise 13
Let W(z)=\sum_{n\ge0}W_n z^n, and define the truncated polynomial
TAOCP 4.7 Exercise 14
Let U(z)=z+U_k z^k+\cdots,\qquad k\ge 2, and define the iterates of $U$ by
TAOCP 4.7 Exercise 15
The key point is to identify correctly what equation (27) says in the Brent-Traub discussion.
TAOCP 4.7 Exercise 16
Define V(t)=t+V_2t^2+V_3t^3+\cdots=t\phi(t), \qquad \phi(t)=1+V_2t+V_3t^2+\cdots.
TAOCP 4.7 Exercise 17
Let V(z)=V_1z+V_2z^2+V_3z^3+\cdots, and define
TAOCP 4.7 Exercise 18
Let F(x,y;z)=\sum_{n\ge0}\frac{V_n(x+y)}{n!
TAOCP 4.7 Exercise 19
Let F(z,u)=\sum_{n\ge0}\frac{V(z)^n}{n!
TAOCP 4.7 Exercise 20
By definition, W(z)=U(V(z)),\qquad U(z)=\sum_{k\ge1}U_kz^k, since $U_0=0$.
TAOCP 4.7 Exercise 21
The proposed solution does not correctly prove the stated matrix-product formula.
TAOCP 4.7 Exercise 22
**Exercise 4.
TAOCP 4.7 Exercise 23
**Exercise 4.
TAOCP 4.7 Exercise 24
Let $U=(u_{nk})$ be the power matrix of $U(z)$.
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
TAOCP 4.7 Exercise 26
Let U(z)=U_0+U_1z+U_2z^2+\cdots , \qquad V(z)=V_1z+V_2z^2+\cdots ,