2
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ It is not that easy. There is the Faa di Bruno's formula, though. $\endgroup$ Jun 10 '16 at 9:08
  • $\begingroup$ @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). $\endgroup$
    – user21820
    Jun 10 '16 at 9:30
3
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ See my answer for how to do exactly what the asker would like to do but purely formally. $\endgroup$
    – user21820
    Jun 10 '16 at 9:21
1
$\begingroup$

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

$\endgroup$
1
  • 1
    $\begingroup$ 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. $\endgroup$
    – M. Vinay
    Jun 10 '16 at 9:22
1
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ 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... $\endgroup$ Jun 11 '16 at 6:57
  • $\begingroup$ @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? $\endgroup$
    – user21820
    Jun 11 '16 at 8:47
  • $\begingroup$ @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. $\endgroup$
    – user21820
    Jun 11 '16 at 8:57
  • $\begingroup$ @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. $\endgroup$
    – user21820
    Jun 11 '16 at 8:59
  • $\begingroup$ @MrTsjolder: By the way, I used different notation because I do not like using round brackets for anything other than grouping. $\endgroup$
    – user21820
    Jun 11 '16 at 9:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.