Composition of formal power series of exp and log

combinatoricsexponential functionlogarithmspower series

I'm considering the formal power series $$\exp(X)=\sum_{n\geq 0} \frac 1 {n!} X^ n\in \mathbb Q [[X]]$$ and $$\log(1+X) =\sum_{n\geq 1} \frac {(-1)^{n-1}}{n} X^n\in \mathbb Q [[X]].$$
The composition of formal power series $f =\sum_{n\geq 0} a_n X^n$ and $g=\sum_{n\geq 1} b_n X^ n$ is defined as follows: For $k\geq 0$ the power series $g^k = \sum_l c_{k,l} X^ l$ is given by the Cauchy product. Note that $c_{k,l}=0$ if $k>l$ since $b_0=0$. Now $$f\circ g(X)=f(g(X)) := \sum_k a_k \sum_l c_{k,l} X^ l = \sum _l \left(\sum_{k=0}^l a_k c_{k,l}\right) X^l.$$ How can I see that $\exp(\log(1+X))=1+X$ as formal power series only using reordering of terms?

I'm also interested in the other composition $\log(\exp(X))=X$ where $\log(\exp(X)=\log (1 + (\exp(X)-1))$ which is well-defined since the power series $\exp(X)-1$ has vanishing absolute term.

Best Answer

I found this solution by modifying episqrt163's excellent answer giving a formal power series proof of $\exp(\log(\frac1{1-x}))=\frac1{1-x}$. \begin{align} \exp(\log(1+x)) &=\sum_{k\ge 0}\frac{1}{k!}\Big(\log(1+x)\Big)^k \\&=\sum_{k\ge 0}\frac1{k!}\left(\sum_{i_1\ge 1}\frac{(-1)^{i_1-1}x^{i_1}}{i_1}\right)\cdots\left(\sum_{i_k\ge 1}\frac{(-1)^{i_k-1}x^{i_k}}{i_k}\right) \\&=\sum_{k\ge 0}\frac1{k!}\sum_{n\ge k}\; x^n\sum_{\substack{i_1+\dots+i_k=n \\ i_1\ge 1,\dots,i_k\ge 1}} \frac{(-1)^{(i_1-1)+\dots+(i_k-1)}}{i_1 i_2\cdots i_k} \\&=\sum_{n\ge 0}x^n\sum_{k=0}^n\frac1{k!}\sum_{\substack{i_1+\dots+i_k=n \\ i_1\ge 1,\dots,i_k\ge 1}}\frac{(-1)^{n-k}}{i_1 i_2\cdots i_k} \end{align} The innermost ranges over compositions of $n$ with exactly $k$ parts. To simplify this unwieldy summation, we will group together all compositions which correspond to the same unordered integer partition.

Let $\lambda=(\lambda_1,\lambda_2,\dots,\lambda_k)$ be an integer partition of $n$ with exactly $k$ parts. Furthermore, define the multiplicity vector $(m_1,\dots,m_n)$ for $\lambda$, where for each $i\in \{1,\dots,n\}$, $m_i$ is the number of parts equal to $i$ in $\lambda$. The number of ordered compositions $(i_1,\dots,i_k)$ corresponding to $\lambda$ when put in sorted order is $$ \frac{k!}{m_1!\cdots m_n!} $$ This implies that we can re-index the summation to range over integer compositions $\lambda$ of $n$ with $k$ parts, as follows: $$ \begin{align} \exp(\log(1+x)) &= \sum_{n\ge 0}x^n\sum_{k=0}^n\frac1{k!}(-1)^{n-k} \sum_{\substack{\lambda \,\vdash n \\ \text{len}(\lambda)=k}} \frac{k!}{m_1!\cdots m_n!}\frac{1}{1^{m_1}\cdots n^{m_n}} \\&= \sum_{n\ge 0}\frac{x^n}{n!}\sum_{k=0}^n (-1)^{n-k} \sum_{\substack{\lambda \,\vdash n \\ \text{len}(\lambda)=k}} \frac{n!}{m_1!1^{m_1}\cdots m_n!n^{m_n}} \end{align} $$ It is well known that $\frac{n!}{m_1!1^{m_1}\cdots m_n!n^{m_n}}$ is equal to the number of permutations with cycle type $\lambda$. Since we are summing over all $\lambda$ with $k$ parts, the innermost sum equals the number of permutations with exactly $k$ cycles, i.e. the unsigned Stirling number of the first kind. That is, $$ \exp(\log(1+x))=\sum_{n\ge 0}\frac{x^n}{n!}\sum_{k=0}^n (-1)^{n-k}{n \brack k} $$ Finally, the alternating sum $\sum_{k=0}^n (-1)^{n-k}{n \brack k}$ is equal to zero for all $n\ge 2$, because it computes the difference between the number of permutations with an even number of cycles and the number of permutations with an odd number of cycles. There is a bijection between these two groups, namely, multiplying by any transposition. The exception is $n=0$ and $n=1$, where $n$ is too small for a transposition to exists. In these cases, the difference is one. This exactly corresponds to the series $$ 1+x+\color{gray}{0x^2+0x^3+\dots}, $$ completing the proof.

Related Question