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

Question

I am trying to prove this directly by comparing the coefficients in the two series rather than using formal calculus.

Here is what I have so far, but I think I made a mistake:

\begin{align*} e^{\log\frac{1}{1-x}} &= \sum_{n\geq0}\frac{1}{n!}\left(\log\frac{1}{1-x}\right)^n\\ &= 1+\sum_{n\ge1}\frac{1}{n!}\sum_{k\geq 1}\sum_{i_1+\dotsb+i_n=k}\frac{x^k}{i_1\dotsb i_n} \end{align*} Is this correct so far? If so, how do I proceed?

EDIT: \begin{align*} \log\left(\frac{1}{1-x}\right) &= \sum_{k\geq1}\frac{x^k}{k}\\ e^x &= \sum_{n\geq 0} \frac{x^n}{n!} \end{align*} The composition is well defined since the constant term of $\log(\frac{1}{1-x})$ is 0.

Answer 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!

Answer 2

A combinatorial proof.

Write $$-\log(1-x)=\sum_{n=1}^{\infty}\frac{(n-1)!}{n!}x^n.$$

The $(n-1)!$ is the number of ways to seat people in a circle of size $n,$ where rotations are considered the same.

So:

$$(-1)^k\log^k(1-x)=\sum_{n=0}^\infty\frac{a_{k,n}}{n!}x^n$$

Where $a_{k,n}$ is the number of ways to seat $n$ people around $k$ ordered circles, no table empty. You have $a_{0,0}=1,$ and $a_{k,n}=0$ for $k<n.$

Then $$\begin{align}\exp(-\log(1-x))&=\sum_{k=0}^{\infty}\frac{1}{k!}\sum_{n=k}\frac{a_{k,n}}{n!}x^n\\ &=\sum_{n=0}^{\infty}\frac{x^n}{n!}\sum_{k=0}^n \frac{a_{k,n}}{k!} \end{align} $$

So you need to prove:

$$\sum_{k=0}^n \frac{a_{k,n}}{k!}=n!\tag1$$ for all $n.$

Once you have that, you get:

$$\exp(-\log(1-x))=\sum_{n=0}^{\infty} x^n=\frac{1}{1-x}.$$

Now, $\frac{a_{k,n}}{k!}$ is the number of ways to arrange $n$ people around $k$ unordered circles.

So we want to find a way to map the set of all permutations of $\{1,2,\dots,n\}$ to the set of all ways to place $n$ people in an unordered set of circles, with any number of circles.

But when we write a permutation as cycles, that is just what we are doing. When $n=6,$ for example, the permutation $(123)(45)(6)$ can be thought of as putting 123 in that order, clockwise, around one circle, $45$ puts people $45$ in one circle, and $6$ sits alone at a circle.

---

The key is the combinatorial treatment of exponential generating functions, and what $f^n(x)$ means when $f(x)$ is a combinatorial generating function.

We can prove the combinatorial definition of $a_{k,n}$ by induction on $k.$ You just need the property that:

$$\sum_{n=0}^\infty \frac{b_n}{n!}x^n\sum_{m=0}^\infty \frac{c_m}{m!}x^m=\sum_{n=0}^{\infty} \frac{x^n}{n!} \sum_{j=0}^n\binom nk b_jc_{n-j}$$

Then if $c_{n}=a_{k,n}$ and $b_n=(n-1)!$ (and $b_0=0.$) Then you get:

$$a_{k+1,n} =\sum_{j=0}^n\binom nj b_ja_{k,n-j}\tag2$$

It is easy to see if $a_{k,n}$ is the number of ways to put $n$ people in $k$ ordered circles, the the sum on the right adds, for each $j,$ the number of ways of putting $j$ people around a first circle, times the number of ways of putting the remains people in $k$ circles.

---

There might be a non-combinatorial proof of $(1)$ directly from the recurrence $(2).$ I don't see it immediate, but it seems like some induction might work.