Extending an Analytic Proof for Lagrange Inversion of Formal Power Series

100 Views Asked by At

In Appendix A.6 of Sedgewick and Flajolet's Analytic Combinatorics, the authors present a proof of the assertion that if we have formal power series $y(z)$ and $\phi(z)$ (where the constant term of the latter series is nonzero) then the identity

$$y(z) = z\cdot \phi(y(z))$$

implies that for each positive integer $n$ we have

$$ [z^n]y(z) = \frac{1}{n}\cdot [z^{n-1}]\phi(z)^n$$

where here $[z^m]A(z)$ denotes the coefficient of $z^m$ in a power series $A\in \mathbb{C}[[z]].$

The proof uses Cauchy's integral formula and a change of variable to prove the result, which I understand.

To justify this use of analysis in an identity we want to hold in general for any formal power series (and this is the part I do not understand), the author's write that because $[z^n]y(z)$ only is a polynomial in $[z^j]\phi(z)$ for $0\le j\le n,$ we can assume without loss of generality that $y$ is a polynomial.

Why is this assumption valid? Why can we use this assumption to make sure the proof works out alright for general formal power series?

For reference, the proof with the Cauchy's integral formula began by writing (where $\mathcal{C}$ is some sufficiently small origin-centered, positively-oriented circle)

$$n\cdot [z^n]y(z) = [z^{n-1}]y'(z) = \frac{1}{2\pi i}\int_{\mathcal{C}} \frac{y'(z)}{z^n}\,\text{d}z .$$

Then by making the substitution $w = y(z)$ and using the fact that $z = w/\phi(w)$ yields

$$n\cdot [z^n]y(z) = \frac{1}{2\pi i}\int_{\mathcal{C}} \frac{y'(z)}{z^n}\,\text{d}z = \frac{1}{2\pi i}\int_{y(\mathcal{C})} \frac{\phi(w)^n}{w^n}\,\text{d}w = [w^{n-1}]\phi(w)^n.$$

Why is it that despite assuming that $y$ is a polynomial, we may assume $y(z) = z\phi(y(z))$ in our change of variable?