On the composition of formal power series

Question

I an attempt to compute the coefficients of the composition $f(g(x))$ of two power series $f(x) = \frac{1}{1-x}$ and $g(x) = \frac{1}{1-x}-1$, I used the definition of composition to get to $$f(g(x)) = \sum_{n=0}^{\infty} \left(\frac{1}{1-x} - 1\right)^n = \sum_{n=0}^{\infty} \left(\frac{x}{1-x}\right)^n$$ but I don't seem to be able to find a way to rewrite this in a way I can get the coefficients out, i.e. something of the form $\sum_{n=0}^\infty c_n x^n$.

Another way to compute the coefficients I know of, could be to use that $f(x) = \sum_{n=0}^\infty x^n$ and $g(x) = \sum_{n=1}^\infty x^n$ and actually compute each $c_N(x) = \sum_{n=0}^N f_n (g(x))^n = \sum_{n=0}^N (g(x))^n$, but this seems cumbersome if you need a lot of coefficients.

Using the transfer principle, on the other hand, one easily can get to $$ f(g(x)) = \frac{1}{1-\frac{1}{1-x} + 1} = \frac{1-x}{1-2x}$$ with expansion $1 + \sum_{n=1}^\infty 2^{n-1} x^n$.

Am I missing something obvious here or is it just not that easy to find the coefficients of the composition of two power series without leaving the "formal world"? I am wondering, because I personally am not the greatest fan of analysis and prefer to think in the formal world

Answer 1

We have $$f(g(x)) = \sum_{k = 0}^\infty \left( \dfrac x {1 - x} \right)^k .$$

Now, for $k \ge 1$, using $\dfrac 1 {(1 - x)^k} = \sum\limits_{m = 0}^\infty \binom{m + k- 1}{m} x^m$, we get

\begin{align*} f(g(x)) & = 1 + \sum_{k=1}^\infty x^k \sum_m \binom{m + k - 1}{m} x^m\\ & = 1 + \sum_{k=1}^{\infty} \sum_m \binom{m + k - 1}{m} x^{m +k}. \end{align*}

To collect together the coefficients of the same power of $x$ in the above summation, let $m + k = n$, to get \begin{align*} f(g(x)) & = 1 + \sum_{n=1}^\infty \sum_{m=0}^{n-1} \binom{n - 1}{m} x^n\\ & = 1 + \sum_{n = 1}^\infty 2^{n-1} x^n, \end{align*}

since $\sum\limits_{m=0}^{n-1} \binom{n - 1}{m} = 2^{n-1}$.

Answer 2

You can do that without leaving the formal world but it is often harder. In general, the formula (or the definition) for the composition $f(g(x))$ when $g(x) = \sum_{n=0}^{\infty} b_n x^n$ and $f(x) = \sum_{n=1}^{\infty} a_n x^n$ is given by

$$ f(g(x)) = \sum_{n=1}^{\infty} a_n \left( \sum_{m=1}^{\infty} b_m x^m \right)^n = \sum_{l=0}^{\infty} c_l x^l, \\ c_l = \sum_{k \in \mathbb{N}, J = (j_1, \dots,j_k) \in \mathbb{N}_{+}^k,|J| = l} b_k a_{j_1} \dots a_{j_k} = \sum_{k \in \mathbb{N}} \sum_{J = (j_1, \dots,j_k) \in \mathbb{N}_{+}^k,|J| = l} b_k a_{j_1} \dots a_{j_k}. $$

The formula is motivated by expanding the powers formally and collecting terms of $x^l$. In your case, $a_n = b_m = 1$ so in order to calculate $c_l$, we need to answer the combinatorial question:

In how many ways we can pick a $k \in \mathbb{N}$ and $j_1, \dots, j_k \geq 1$ such that $j_1 + \dots + j_k = l$. Obviously we must have $k \leq l$ and for a fixed $k$, the answer is precisely ${l - 1 \choose k - 1}$. Thus,

$$ c_l = \sum_{k=1}^l {l - 1 \choose k - 1} = 2^{l-1}.$$

Answer 3

If you don't want to leave the formal world, you still have a very simple alternative, namely to work in an extension of formal power series. A formal power series is a sequence of coefficients that is added and multiplied as if it were an (infinite-degree) polynomial in some indeterminate, say $X$. Let us denote this structure by $F^*[X]$, analogously to the collection of polynomials in $X$ over $F$, denoted by $F[X]$. You can then consider the collection of all (infinite-degree) rational functions in $X$, and define addition and multiplication on them in the obvious way, and prove that the resulting structure is a field, which we shall denote by $F^*(X)$, analogously to the field of rational functions in $X$ over $F$, denoted by $F(X)$. Note that $F^*(X)$ is a field for much the same reason as that $F(X)$ is a field. $F^*[X]$ and $F(X)$ both embed into $F^*(X)$, so your question from the very beginning can be stated and proven in the larger structure.