I am trying to understand the discussion in my course notes about algebraic manipulation of generating functions.
Below I've pasted the whole section, though my confusion is greatest regarding the part that starts with "To illustrate this" and continues until the end.
Excerpt:
Discussion:
I don't understand what is being illustrated in the section beginning with "To illustrate this". Are $1 + x, 1 + x – x^2$ and $1 + x – x^2 + x^4$ supposed to be successive approximations to $f^{-1}(x)$?
I tried to figure out what, in general, the inverse of a formal Laurent series would look like, and I came up with the following:
To find the inverse of the Laurent series $f(x) = a_k x^k + a_{k + 1} x^{k + 1} + \dots$, we seek a Laurent series $g(x) = b_l x^l + b_{l + 1} x^{l + 1} + \dots$ such that multiplying the two together in either order produces the Laurent series with 1 in position zero and 0 in all other places. Given our understanding of multiplication, that means we desire a series with coefficients such that $\sum_{j \in \mathbb Z} p_j q_{0 – j} = 1$, and $\sum_{j \in \mathbb Z} p_j q_{n – j} = 0$ for all other $n$.
For the zero position of the product we want 1, so it makes sense to let the first term for $g$ be $a_k^{-1}x^{-k}$. That way, the multiplication produces 1 for the 0th term.
For the one position of the product we want 0, so that means we need $p_k q_{1 – k} + p_{k + 1} q_{1 – (k + 1)} = 0$, or $p_k q_{-k + 1} + p_{k + 1} q_{-k} = 0$, which implies that $q_{-k + 1} = – \frac{p_{k + 1} q_{-k}}{p_k}$, so the second term of $g$ will be $- \frac{p_{k + 1} q_{-k}}{p_k} x^{-k + 1}$.
For the two position of the product we want 0, so following the same pattern, we need $p_k q_{2 – k} + p_{k + 1} q_{2 – (k + 1)} + p_{k + 2} q_{2 – (k + 2)} = 0$, or $p_k q_{-k + 2} + p_{k + 1} q_{-k + 1} + p_{k + 2} q_{-k} = 0$, which implies that $q_{-k + 2} = – \frac{p_{k + 1} q_{-k + 1} + p_{k + 2} q_{-k}}{p_k}$, so the second term of $g$ will be $- \frac{p_{k + 1} q_{-k + 1} + p_{k + 2} q_{-k}}{p_k} x^{-k + 2}$. Thus, we should have
\begin{align*}
g(x) &= a_k^{-1}x^{-k} – \frac{p_{k + 1} q_{-k}}{p_k} x^{-k + 1} – \frac{p_{k + 1} q_{-k + 1} + p_{k + 2} q_{-k}}{p_k} x^{-k + 2} – \dots
\end{align*}although I should really translate it into terms of $a$, which gives me
\begin{align*}
g(x) &= a_k^{-1}x^{-k} – \frac{a_{k + 1} a_k^{-1}}{a_k} x^{-k + 1} – \frac{a_{k + 1} \frac{a_{k + 1} a_k^{-1}}{a_k} + a_{k + 2} a_k^{-1}}{a_k} x^{-k + 2} – \dots.
\end{align*}
Unfortunately, when I let $f(x) = 1 – x + 2x^2 – 3x^3 + 4x^4 – \dots$ as in the notes above, and then try to use the formula I've derived, I end up with $f^{-1}(x) = 1 + x – 3x^2 \dots$, which doesn't match the approximations given. But I'm not even sure what the approximations are supposed to be approximating, so I don't know if there is a problem or not.
I appreciate any responses regarding my confusion and corrections regarding my derivation of the inverse Laurent series more generally.
Best Answer
Yes, $1+x$, $1+x-x^2$, and $1+x-x^2+x^4$ are successive approximations to $f^{-1}(x)$; this is a bit clearer, I think, if one writes $\frac1{f(x)}$ instead of $f^{-1}(x)$. Notice that the products of these three polynomials with $f(x)$ progressively eliminate the $x$ term, the $x^2$ and $x^3$ terms, and the $x^4$ term. This is an example of the term-by-term algorithm for finding $\frac1{f(x)}$. It is perhaps a little unfortunate that the example is an ordinary power series: an example starting with an $x^{-2}$ term, say, might be more helpful.
What you’re trying to do in the long block quote at the end is fine, and
$$-\frac{p_{k+1}q_{-k+1}+p_{k+2}q_{-k}}{p_k}x^{-k+2}$$
is correct: in the example it evaluates to
$$-\frac{(-1)(1)+(2)(1)}1x^2=-x^2\,,$$
as it should. It appears that when you translated it back to $a_i$ coefficients you inadvertently changed the sign of $q_{-k+1}$.