TAOCP 4.7 Exercise 18

Section 4.7: Manipulation of Power Series

Exercise 18. [**] [HM23] Continuing exercise 17, prove that poweroids also satisfy

$$xV_n(x+y) = (x+y)\sum_{k}\binom{n-1}{k-1}V_k(x)V_{n-k}(y).$$

[Hint: Consider the derivative of $e^{V(z)}$.]

Verified: yes
Solve time: 1m36s

---

Let

$$ F(x,y;z)=\sum_{n\ge0}\frac{V_n(x+y)}{n!}z^n . $$

By the definition of the power matrix,

$$ \frac{V_n(x)}{n!}=[z^n]e^{xV(z)}, $$

hence

$$ F(x,y;z)=e^{(x+y)V(z)}. $$

Differentiating with respect to $z$,

$$ (x+y)V'(z)e^{(x+y)V(z)} =\sum_{n\ge1}\frac{V_n(x+y)}{(n-1)!}z^{,n-1}. $$

Multiplying by $x$ and using

$$ xV'(z)e^{xV(z)} =\frac{d}{dz}e^{xV(z)} =\sum_{k\ge1}\frac{V_k(x)}{(k-1)!}z^{,k-1}, $$

together with

$$ e^{yV(z)} =\sum_{m\ge0}\frac{V_m(y)}{m!}z^m, $$

gives

$$ x\sum_{n\ge1}\frac{V_n(x+y)}{(n-1)!}z^{,n-1} =(x+y)\Bigl(\sum_{k\ge1}\frac{V_k(x)}{(k-1)!}z^{,k-1}\Bigr) \Bigl(\sum_{m\ge0}\frac{V_m(y)}{m!}z^m\Bigr). $$

Equating coefficients of $z^{,n-1}$,

$$ \frac{xV_n(x+y)}{(n-1)!} =(x+y)\sum_{k=1}^{n} \frac{V_k(x)}{(k-1)!}, \frac{V_{n-k}(y)}{(n-k)!}. $$

Since

$$ \frac{(n-1)!}{(k-1)!(n-k)!} =\binom{n-1}{k-1}, $$

multiplication by $(n-1)!$ yields

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

Therefore

$$ \boxed{; xV_n(x+y) = (x+y)\sum_{k} \binom{n-1}{k-1} V_k(x)V_{n-k}(y) ;} $$

for all $n\ge1$. This completes the proof.

∎