Inverse of a formal power series ($f(x{)}^{-1}$)

Here an inverse of a formal power series means its multiplicative inverse: $f(x{)}^{-1}f(x)=1$. The formal power series reciprocal exists exactly when the constant coefficient of $f$ is a unit in the coefficient ring. Thus $1-x$ is invertible in $\mathbb{Z}[[x]]$, while $2+x$ is not, though it is invertible in $\mathbb{Q}[[x]]$.

A compositional inverse solves $f(g(x))=x$, which is a different problem. For instance, the multiplicative inverse of $1-x$ is $1+x+x^2+\cdots$, whereas the compositional inverse of $x+x^2$ starts $x-x^2+2x^3-\cdots$. Stating which operation is inverted prevents a common ambiguity.

Suppose $f$ is a formal power series with invertible constant coefficient and $g$ satisfies $fg\equiv 1(\mathrm{mod}{x}^m)$. The updateis an inverse modulo $x^{2m}$, because $1-f{g}_{\mathrm{new}}=(1-fg{)}^2$ before truncation. Each update doubles the number of correct coefficients.

Start with the inverse of the constant coefficient and repeat, truncating all products to the required order. For $f=1-x$, the first approximations are $1$, $1+x$, and $1+x+x^2+x^3$. With a polynomial multiplication cost $M(n)$ satisfying the usual growth assumptions, computing the first $n$ coefficients takes $O(M(n))$ operations. The identity is algebraic and remains valid in characteristic two.