On the composition of formal power series

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

• It is not that easy. There is the Faa di Bruno's formula, though. Jun 10 '16 at 9:08
• @IvanNeretin: It's not easy in general, but for composition of rational functions it's as easy as how the asker did it (see my answer). Jun 10 '16 at 9:30

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}.$$

• See my answer for how to do exactly what the asker would like to do but purely formally. Jun 10 '16 at 9:21

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}$.

• If it's difficult to deal with the general form of the summation terms, expand the double summation in several rows, with $k$ increasing along the each row, and $m$ from the first row to the lower rows. \begin{align*} \sum_{k=1}^\infty \sum_{m=0}^\infty \binom{m+k-1}{m} x^{m+k} = & \binom{0}{0} x + \binom{1}{0} x^2 + \binom{2}{0} x^3 + \cdots\\ & + \binom{1}{1} x^2 + \binom{2}{1} x^3 + \binom{3}{1} x^4 + \cdots\\ & + \binom{2}{2} x^3 + \binom{3}{2} x^4 + \binom{4}{2} x^5 \cdots\\ & \qquad \qquad \qquad \vdots \end{align*} Then collect the coefficients of each power of $x$ and generalize. Jun 10 '16 at 9:22

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.

• I am afraid I can't follow completely there. Is this structure $F^*[X]$ something like the structure of the formal power series (we wrote $F[[x]]$ and proved that it is not a field)? I have this feeling the $F^*(X)$ tends towards formal Laurent Series (we wrote $F((x))$), but then I don't see how that could bring me to the coefficients... Jun 11 '16 at 6:57
• @MrTsjolder: An ordinary polynomial is a finite sequence, with addition and multiplication defined as if it is the sequence of coefficients of $X$. We denote that by $F[X]$. We can do the same with infinite sequences, with pointwise addition and $(f \cdot g)(i) = \sum_{i=0}^k f(i) g(k-i)$. That gives us exactly the formal power series, which I never said was a field. But we can go further to rational functions. Do you know what are rational functions? Jun 11 '16 at 8:47
• @MrTsjolder: $F^*(X)$ is simply the field of fractions of $F^*[X]$, which is equivalent to formal Laurent series in $X$. The whole point is that in your question "$\frac{1}{1-X}$" is technically merely notation denoting the formal power series, and is not a result of dividing $1$ by $1-X$. But if you work in $F^*(X)$ from the beginning, then it literally is since $F^*(X)$ is a field. Then you can compute $f \circ g$ trivially in the exact manner you desire, because you are just using field operations! Finally, you can use $\frac{1}{1-2X} = 1 + 2X + 4X^2 + \cdots$ in $F^*(X)$ to finish. Jun 11 '16 at 8:57
• @MrTsjolder: If the last part is not clear, it is because every equality you prove in $F^*(X)$ that can be stated in $F^*[X]$ is trivially true there as well via the embedding. Jun 11 '16 at 8:59
• @MrTsjolder: By the way, I used different notation because I do not like using round brackets for anything other than grouping. Jun 11 '16 at 9:01