Stirling numbers of first kind in a power series

Question

We need to prove that $\cfrac{(-\ln{(1-x)})^k}{k!}=\displaystyle\sum_{n=k}^\infty \begin{bmatrix} n\\ k \end{bmatrix}\cfrac{x^n}{n!}$. For this, I've done induction in $k$. The case $k=1$ is trivial. When I do the inductive step, I consider the next: \begin{equation} \begin{split} \cfrac{(-\ln{(1-x)})^{k+1}}{(k+1)!}&=\left(\cfrac{(-\ln{(1-x)})^k}{k!}\right)\left(\cfrac{-\ln{(1-x)}}{k+1}\right)\\ &=\frac{1}{k+1}\left(\sum_{n=k}^\infty\begin{bmatrix} n\\ k \end{bmatrix}\frac{x^n}{n!}\right)\left(\sum_{n=1}^{\infty}\frac{x^n}{n}\right)\\ &=\frac{1}{k+1}\sum_{n=k+1}^\infty x^n\sum_{m=k}^{n-1} \begin{bmatrix} m\\ k \end{bmatrix}\frac{1}{(n-m)m!}. \end{split} \end{equation} So, now my problem is showing that $\cfrac{n!}{k+1}\displaystyle\sum_{m=k}^{n-1}\begin{bmatrix} m\\ k \end{bmatrix}\frac{1}{(n-m)m!}=\begin{bmatrix} n\\ k+1 \end{bmatrix}$. On other hand, with the recurrence relation we can deduce the next: \begin{equation} \begin{split} \begin{bmatrix} n\\ k+1 \end{bmatrix}&=\begin{bmatrix} n-1\\ k \end{bmatrix}+(n-1)\begin{bmatrix} n-1\\ k+1 \end{bmatrix}\\ &=\begin{bmatrix} n-1\\ k \end{bmatrix}+(n-1)\left(\begin{bmatrix} n-2\\ k \end{bmatrix}+(n-2)\begin{bmatrix} n-2\\ k+1 \end{bmatrix}\right)\\ &=\begin{bmatrix} n-1\\ k \end{bmatrix}+(n-1)\begin{bmatrix} n-2\\ k \end{bmatrix}+(n-1)(n-2)\begin{bmatrix} n-2\\ k+1 \end{bmatrix}\\ &\ \ \vdots\\ &=\frac{(n-1)!}{(n-1)!}\begin{bmatrix} n-1\\ k \end{bmatrix}+\frac{(n-1)!}{(n-2)!}\begin{bmatrix} n-2\\ k \end{bmatrix}+\frac{(n-1)!}{(n-3)!}\begin{bmatrix} n-3\\ k \end{bmatrix}+\ldots + \frac{(n-1)!}{k!}\begin{bmatrix} k\\ k \end{bmatrix}\\ &=(n-1)!\sum_{m=k}^{n-1}\frac{1}{m!}\begin{bmatrix} m\\ k \end{bmatrix}. \end{split} \end{equation}

Answer 1

We seek to prove that

$$\frac{1}{k!} \left(\log\frac{1}{1-z}\right)^k = \sum_{n\ge k} {n\brack k} \frac{z^n}{n!}$$

by induction. We get for the base case

$$\log\frac{1}{1-z} = \sum_{n\ge 1} \frac{z^n}{n}$$

which holds by inspection. We also have

$$n! [z^n] \frac{1}{(k+1)!} \left(\log\frac{1}{1-z}\right)^{k+1} \\ = (n-1)! [z^{n-1}] \left(\frac{1}{(k+1)!} \left(\log\frac{1}{1-z}\right)^{k+1}\right)' \\ = (n-1)! [z^{n-1}] \left(\frac{1}{k!} \left(\log\frac{1}{1-z}\right)^{k}\right) \left(\log\frac{1}{1-z}\right)' \\ = (n-1)! [z^{n-1}] \left(\frac{1}{k!} \left(\log\frac{1}{1-z}\right)^{k}\right) \frac{1}{1-z}.$$

We now use the induction hypothesis and the fact that we have a convolution of two EGFs to get for the coefficient being extracted

$$\sum_{q=k}^{n-1} {n-1\choose q} {q\brack k} (n-1-q)!$$

We may now conclude by combinatorics, re-writing the sum as follows:

$$\sum_{q=k}^{n-1} {n-1\choose n-1-q} (n-1-q)! {q\brack k}$$

Here we are counting partitions of $[n]$ into $k+1$ cycles by classifying according to the cycle where $n$ resides. We choose $n-1-q$ companions on that cycle where each choice generates $(n-q)!/(n-q)$ possible cycles. The remaining $q$ elements are partitioned into $k$ cycles. In this way we have counted all ${n\brack k+1}$ partitions exactly once, and we have the claim.

We may also continue algebraically using the OGF of the Stirling numbers of the first kind:

$$\sum_{q=k}^{n-1} {n-1\choose n-1-q} (n-1-q)! [w^k] {w+q-1\choose q} q! \\ = (n-1)! [w^k] \sum_{q=k}^{n-1} {w+q-1\choose q}.$$

Now

$$\sum_{q\ge 0} {w+q-1\choose q} z^q = \frac{1}{(1-z)^w}$$

so we get

$$(n-1)! [w^k] [z^{n-1}] \frac{1}{(1-z)^{w+1}} - (n-1)! [w^k] [z^{k-1}] \frac{1}{(1-z)^{w+1}} \\ = (n-1)! [w^k] {w+n-1\choose n-1} - (n-1)! [w^k] {w+k-1\choose k-1} \\ = (n-1)! [w^k] \frac{n}{w} {w+n-1\choose n} = n! [w^{k+1}] {w+n-1\choose n} = {n\brack k+1}.$$

Remark. In the induction step we have used the fact that when we multiply two exponential generating functions of the sequences $\{a_n\}$ and $\{b_n\}$ we get that

$$ A(z) B(z) = \sum_{n\ge 0} a_n \frac{z^n}{n!} \sum_{n\ge 0} b_n \frac{z^n}{n!} = \sum_{n\ge 0} \sum_{k=0}^n \frac{1}{k!}\frac{1}{(n-k)!} a_k b_{n-k} z^n\\ = \sum_{n\ge 0} \sum_{k=0}^n \frac{n!}{k!(n-k)!} a_k b_{n-k} \frac{z^n}{n!} = \sum_{n\ge 0} \left(\sum_{k=0}^n {n\choose k} a_k b_{n-k}\right)\frac{z^n}{n!}.$$