Calculating the coefficient of $x^k$

Question

In order to calculate the coefficient of $x^k$ in the sum $$\sum_{n\geq 1} \frac {\big(-(\frac {x}{1!}+\frac {x^2}{2!}+\cdots )\big)^n}{n}=\frac {-1}{1}\big(\frac {x}{1!}+\frac {x^2}{2!}+\cdots \big)+\frac {(-1)^2}{2}\big(\frac {x}{1!}+\frac {x^2}{2!}+\cdots \big)^2+\cdots +\frac {(-1)^n}{n}\big(\frac {x}{1!}+\frac {x^2}{2!}+\cdots \big)^n+\cdots $$ , we just need to find the coefficient of $x^k$ in $$\frac {(-1)^n}{n}\big(\frac {x}{1!}+\frac {x^2}{2!}+\cdots \big)^n \quad , \text {when} \quad n\leq k$$

So, $$\sum_{1b_1+2b_2+\cdots +(k-n)(b_{k-n})=k} \binom {n}{b_1}x^{b_1\cdot 1}\binom {n-b_1}{b_2}\dfrac {(x)^{b_2\cdot 2}}{(2!)^{b_2}}\binom {n-b_1-b_2}{b_3}\dfrac {(x)^{b_3\cdot 3}}{(3!)^{b_3}}\cdots n \dfrac {x^{\big(k-n\big)\big(b_{k-n}\big)}}{\big(k-n\big)!} \tag {*}$$

These are in my lecture notes, and I didn't understand the starred part. How is that obtained?

Answer 1

Observe we have \begin{align} \left(\sum^\infty_{i=1} \frac{x^i}{i!} \right)^n = \underbrace{\left(\sum^\infty_{i_1=1} \frac{x^{i_1}}{i_1!} \right)\cdots \left(\sum^\infty_{i_n=1} \frac{x^{i_n}}{i_n!} \right)}_{n-\text{times}} \end{align} which we would like to rewrite in the form \begin{align} \left(\sum^\infty_{i_1=1} \frac{x^{i_1}}{i_1!} \right)\cdots \left(\sum^\infty_{i_n=1} \frac{x^{i_n}}{i_n!} \right)=\sum^\infty_{k=n} c_k x^k. \end{align} Naively, it's clear that \begin{align} \left(\sum^\infty_{i_1=1} \frac{x^{i_1}}{i_1!} \right)\cdots \left(\sum^\infty_{i_n=1} \frac{x^{i_n}}{i_n!} \right) = \sum^\infty_{k=n}\left(\sum_{i_1+\ldots + i_n=k}\frac{1}{i_1!\ldots i_n!} \right)x^k. \end{align} However, we would like to use a more combinatorical argument to rewrite the coefficient.

First, fix some $k\geq n$.

Viewing each $\left(\sum^\infty_{i_j=1} \frac{x^{i_j}}{i_j!} \right)$ as a "basket" we see that the maximum term which we can consider is $x^{k-n+1}$ from this basket. For instance, as remarked by @N.Shales, if I consider $i_1 = k-n+1$, then $i_2=\cdots=i_n = 1$. This little observation allows us to truncate each summation so we can consider \begin{align} \left(\sum^{k-n+1}_{i_1=1} \frac{x^{i_1}}{i_1!} \right)\cdots \left(\sum^{k-n+1}_{i_n=1} \frac{x^{i_n}}{i_n!} \right). \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (\ast) \end{align}

Let us note that we only care about the coefficient of $x^k$ from $\ (\ast)$, but this amounts to finding the number of ways of choosing $b_1\geq 1$ numbers of $x^1$ from $n$ baskets, number of ways of choosing $b_2\geq 2$ numbers of $x^2/2!$ from $n$ baskets, etc, so that \begin{align} b_1+ b_2 \ldots + b_{k-n+1} = n\\ 1\cdot b_1 + 2\cdot b_2 + \ldots + (k-n+1)\cdot b_{k-n+1} =k \end{align} This is precisely given by \begin{align} &\sum_{1\cdot b_1 +\ldots + (k-n+1)\cdot b_{k-n+1}=k} \binom{n}{b_1}\underbrace{x^1\cdots x^1}_{b_1-\text{times}} \binom{n-b_1}{b_2}\underbrace{\frac{x^{2}}{2!}\cdots \frac{x^{2}}{2!}}_{b_2-\text{times}}\cdots \binom{n-b_1-\ldots-b_{k-n}}{b_{k-n+1}}\underbrace{\frac{x^{k-n+1}}{(k-n+1)!}\cdots \frac{x^{k-n+1}}{(k-n+1)!}}_{b_{k-n+1}-\text{times}}\\ =&\ \sum_{1\cdot b_1 +\ldots + (k-n+1)\cdot b_{k-n+1}=k} \binom{n}{b_1}x^{1\cdot b_1}\binom{n-b_1}{b_2}\left(\frac{x^{2}}{2!}\right)^{b_2}\cdots \binom{n-b_1-\ldots-b_{k-n}}{b_{k-n+1}}\left(\frac{x^{k-n+1}}{(k-n+1)!}\right)^{b_{k-n+1}}. \end{align}

Answer 2

Hint: By using the Taylor expansion of the exponential function you can rewrite the first sum as:

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

Compare this to the Taylor series of

$$-\ln(1-u)=\sum_{n=1}^{\infty}\dfrac{u^n}{n},$$

which is valid if $|u|<1$.

Hence we obtain for $u=1-\exp(x)$ for $|1-\exp(x)|<1$

$$\sum_{n=1}^{\infty}\dfrac{(1-\exp(x))^n}{n}=-\ln\left(1-(1-\exp(x))\right)=x.$$