Prove that $\exp(\log(\frac{1}{1-x})) = \frac{1}{1-x}$

Solution 1:

I think everything is quite ok so far (besides maybe the index part, which could be written a little bit more rigidly). In order to show that

\begin{align*} \exp\left(\log\left(\frac{1}{1-x}\right)\right)=\frac{1}{1-x} \end{align*}

we could proceed as follows:

\begin{align*} \exp&\left(\log\left(\frac{1}{1-x}\right)\right)\\ &=\sum_{n\geq0}\frac{1}{n!}\left(\log\frac{1}{1-x}\right)^n\\ &= 1+\sum_{n\ge1}\frac{1}{n!}\left(\sum_{i_1\geq 1}\frac{x^{i_1}}{i_1}\right)\cdot\ldots\cdot\left(\sum_{i_n\geq 1}\frac{x^{i_n}}{i_n}\right)\\ &= 1+\sum_{n\ge1}\frac{1}{n!}\sum_{k\geq n}\sum_{{i_1+\ldots+i_n=k}\atop{i_1\geq 1,\ldots, i_n \geq 1}}\frac{x^k}{i_1\cdot\ldots\cdot i_n}\\ &= 1+\sum_{k\ge1}x^k\sum_{n=1}^{k}\frac{1}{n!}\sum_{{i_1+\ldots+i_n=k}\atop{i_1\geq 1,\ldots, i_n \geq 1}}\frac{1}{i_1\cdot\ldots\cdot i_n}\tag{1}\\ \end{align*}

Observe, the sums were exchanged in $(1)$.

To proceed conveniently, I will interchange the indices $n$ and $k$. We get

\begin{align*} \exp&\left(\log\left(\frac{1}{1-x}\right)\right)\\ &= 1+\sum_{n\ge1}x^n\sum_{k=1}^{n}\frac{1}{k!}\sum_{{i_1+\ldots+i_k=n}\atop{i_1\geq 1,\ldots, i_k \geq 1}}\frac{1}{i_1\cdot\ldots\cdot i_k}\tag{2}\\ &= 1+\sum_{n\ge1}x^n\sum_{k=1}^{n} \sum_{{j_1+\ldots+j_n=k}\atop{{j_1+2j_2+\ldots+n j_n=n}\atop{j_1\geq 0,\ldots, j_n \geq 0}}} \frac{1}{j_1!1^{j_1}\cdot\ldots\cdot j_n!n^{j_n}}\tag{3}\\ &= 1+\sum_{n\ge1}\frac{x^n}{n!}\sum_{k=1}^{n} \sum_{{j_1+\ldots+j_n=k}\atop{{j_1+2j_2+\ldots+n j_n=n}\atop{j_1\geq 0,\ldots, j_n \geq 0}}} \frac{n!}{j_1!1^{j_1}\cdot\ldots\cdot j_n!n^{j_n}}\tag{4}\\ &= 1+\sum_{n\ge1}\frac{x^n}{n!}\sum_{k=1}^{n}|s(n,k)|\tag{5}\\ &= 1+\sum_{n\ge1}x^n\tag{6}\\ &=\frac{1}{1-x} \end{align*}

So, we have proved the question.

Some remarks to the transformations $(2)$ to $(6)$

Observe the considerable change of index variables in the step from $(2)$ to $(3)$.

In $(2)$ there is with $1 \leq k \leq n$: $$\frac{1}{k!}\sum_{{i_1+\ldots+i_k=n}\atop{i_1\geq 1,\ldots, i_k \geq 1}}\frac{1}{i_1\cdot\ldots\cdot i_k}$$ and so we sum up over all compositions of $n$ containing exactly $k$ (non-negative) parts, whereby composition means, that the order of parts matters.

Now we observe:

In $(3)$ each composition $i_1+\ldots+i_k=n$ contains $j_1$ $1$s, $j_2$ $2$s, up to $j_n$, $n$s with $j_l \geq 0$. Since we consider a composition of $n$ we get $$j_1 + 2 j_2 + \ldots + n j_n = n$$ Since the compositions under consideration contain exactly $k$ summands we get $$j_1 + j_2 + \ldots + j_n = k$$ while the other $n-k$ summands are equal to $0$. Therefore we sum up $$\sum_{{j_1+\ldots+j_n=k}\atop{{j_1+2j_2+\ldots+n j_n=n}\atop{j_1\geq 0,\ldots, j_n \geq 0}}} \frac{1}{j_1!1^{j_1}\cdot\ldots\cdot j_n!n^{j_n}}$$ Here, we again sum up over all compositions of $n$ containing exactly $k$ (non-negative) parts.

Some gory details: A factor $j_l!j_l^m$ in the denominator respects all compositions with $m$ summands of size $j_l$ . Since each of these $m$ summands corresponds to a factor in the denominator in $(2)$, we have therefore $j_l^m$ in the denominator of $(3)$. The numerator in $(2)$ divided by $k!$ gives the portion of all $k!$ permutations whereby interchange of equal summands is identified. In $(3)$ the same is done by respecting exactly the equal summands.

I think to better understand what's going on, it's instructive to see an example:

Example for $n=5$ (corresponding to (2)):

\begin{align*} k &\quad i_1+i_2+\cdots+i_k=5 &a_k=\frac{1}{k!}& \left(\frac{1}{i_1\cdot\ldots\cdot i_k}\right)&5!a_k\\ \hline\\ 1&\quad5&\frac{1}{1!}&\left(\frac{1}{5}\right)&24\\ 2&\quad1+4&\frac{1}{2!}&\left(\frac{2}{1\cdot4}\right)&30\\ 2&\quad2+3&\frac{1}{2!}&\left(\frac{2}{2\cdot3}\right)&20\\ 3&\quad1+1+3&\frac{1}{3!}&\left(\frac{3}{1\cdot1\cdot3}\right)&20\\ 3&\quad1+2+2&\frac{1}{3!}&\left(\frac{3}{1\cdot2\cdot2}\right)&15\\ 4&\quad1+1+1+2&\frac{1}{4!}&\left(\frac{4}{1\cdot1\cdot1\cdot2}\right)&10\\ 5&\quad1+1+1+1+1&\frac{1}{5!}&\left(\frac{1}{1\cdot1\cdot1\cdot1\cdot1}\right)&1\\ \end{align*}

Example for $n=5$ (corresponding to (3)):

\begin{align*} k&\quad j_1+2j_2+3j_3+4j_4+5 j_5=5&b_k=&\frac{1}{j_1!1^{j_1}\cdot\ldots\cdot j_n!n^{j_n}}&5!b_k\\ &\quad j_1+j_2+j_3+j_4+ j_5=k&&&\\ \hline\\ 1&\quad (0,0,0,0,1)&&\frac{1}{1!5^1}&24\\ 2&\quad (1,0,0,1,0)&&\frac{1}{1!1^1 1!4^1}&30\\ 2&\quad (0,1,1,0,0)&&\frac{1}{1!2^1 1!3^1}&20\\ 3&\quad (2,0,1,0,0)&&\frac{1}{2!1^21!3^1}&20\\ 3&\quad (1,2,0,0,0)&&\frac{1}{1!1^1 2!2^2}&15\\ 4&\quad (3,1,0,0,0)&&\frac{1}{3!1^3 1!2^1}&10\\ 5&\quad (5,0,0,0,0)&&\frac{1}{5!1^5}&1\\ \end{align*}

Observe, that the values $a_k$ and $b_k$ in each row coincide.

In $(3)$ the fraction is expanded by $n!$ to get a fine combinatorial interpretation in terms of permutations with corresponding cycles:

According to section $6.2$ of Advanced Combinatorics from Louis Comtet we get the following definition and theorem:

Definition: Let $j_1,j_2,\dots,j_n$ be integers $\geq 0$ such that: $$j_1+2 j_2+\cdots+n j_n=n$$ A permutation $\sigma\in\mathcal{S}(N),|N|=n$ is said to be of type $(j_1,j_2,\dots,j_n)$ if its decomposition into disjoint cycles contains exactly $j_l$ cycles of length $l,l=1,2,3,\dots,n$. And he proceeds (Theorem B):

The number of permutations of type $(j_1,j_2,\dots,j_n)$ equals \begin{align*} \frac{n!}{j_1!1^{j_1}\cdot\ldots\cdot j_n!n^{j_n}}\tag{7} \end{align*}

Now observe, that we sum up in $(4)$ over all possible cycles over all lengths from $1\leq k \leq n$, i.e. we sum up over all $n!$ permutations, which results in the simplification in $(6)$.

The reason for introducing $s(n,k)$ in $(5)$ is presented in the rest of the answer.

Note: When we are talking in $(7)$ about the number of permutations with certain cycle types we have to mention the important Stirling numbers of the first kind. In fact the whole question and answer is permanently about these numbers and the signless variant of them. Theorem D in section $6.2$ from Advanced Combinatorics states:

The number of permutation of $n$ whose decomposition has $k$ cycles equals the unsigned Stirling number of the first kind $|s(n,k)|$

$$|s(n,k)|=\sum_{{j_1+\ldots+j_n=k}\atop{{j_1+2j_2+\ldots+n j_n=n}\atop{j_1\geq 0,\ldots, j_n \geq 0}}} \frac{n!}{j_1!1^{j_1}\cdot\ldots\cdot j_n!n^{j_n}}$$

See the corresponding entries for $|s(n,k)|$ from the example $n=5$:

\begin{align*} k&\quad j_1+2j_2+3j_3+4j_4+5 j_5=5 &&\frac{5!}{j_1!1^{j_1}\cdot\ldots\cdot j_n!n^{j_n}}&&|s(n,k)|\\ &\quad j_1+j_2+j_3+j_4+ j_5=k&&\\ \hline\\ 1&\quad (0,0,0,0,1)&&24&&24\\ 2&\quad (1,0,0,1,0)&&30&&50=30+20&\\ 2&\quad (0,1,1,0,0)&&20&&&\\ 3&\quad (2,0,1,0,0)&&20&&35=20+15&\\ 3&\quad (1,2,0,0,0)&&15&&&\\ 4&\quad (3,1,0,0,0)&&10&&10&\\ 5&\quad (5,0,0,0,0)&&1&&1&\\ \end{align*}

To finally close the circle: Comtet presents in section $5.5$ the double generating function for $s(n,k)$, which is directly related to the expression $\exp(\log(\frac{1}{1-x}))$ of our question:

A double generating function for the Stirling Numbers of the first kind is

\begin{align*} \Psi(x,y)&=(1+x)^y\\ &=\sum_{n\geq 0}\left(\sum_{k \geq 0}s(n,k)y^k\right)\frac{x^n}{n!}\\ &=1+\sum_{n\geq 1}\left(\sum_{k=1}^{n}s(n,k)y^k\right)\frac{x^n}{n!}\\ \end{align*}

Since $(1+x)^y=\exp\left(y \log(1+x)\right)$ he presents as vertical generating function for $s(n,k)$:

\begin{align*} \Psi_k(x,y)&=\sum_{n\geq k}s(n,k)\frac{x^n}{n!}\\ &=\frac{1}{k!}\left(\log(1+x)\right)^k \end{align*}

It can be easily shown, that the signless Stirling number of the first kind are $|s(n,k)|=(-1)^{n-k}s(n,k)$. We have therefore according to our question:

\begin{align*} \Psi(-x,-y)&=(1-x)^{-y}\\ &=e^{y\log\frac{1}{1-x}}\\ &=\sum_{k\geq 0}\frac{y^k}{k!}\left(\log\frac{1}{1-x}\right)^k\\ &=\sum_{k\geq 0}y^k\Psi_k(-x,-y)\\ &=\sum_{k\geq 0}y^k\sum_{n\geq k}|s(n,k)|\frac{x^n}{n!}\\ \end{align*}

Note: Please note, that much more can be said about the Stirling numbers of the first and second kind. Comtet devotes a whole chapter exclusively to these numbers!