# Generating function of Lah numbers

Let $L(n,k)\!\in\!\mathbb{N}_0$ be the Lah numbers. We know that they satisfy $$L(n,k)=L(n\!-\!1,k\!-\!1)+(n\!+\!k\!-\!1)L(n\!-\!1,k)$$ for all $n,k\!\in\!\mathbb{Z}$. How can I prove $$\sum_nL(n,k)\frac{x^n}{n!}=\frac{1}{k!}\Big(\frac{x}{1-x}\Big)^k$$ without using the explicit formula $L(n,k)\!=\!\frac{n!}{k!}\binom{n-1}{k-1}$?

Attempt 1: $\text{LHS}=\sum_nL(n\!-\!1,k\!-\!1)\frac{x^n}{n!}+\sum_n(n\!+\!k\!-\!1)L(n\!-\!1,k)\frac{x^n}{n!}\overset{i.h.}{=}?$

Attempt 2: $\text{RHS}\overset{i.h.}{=}$ $\frac{1}{k}\frac{x}{1-x}\sum_nL(n,k\!-\!1)\frac{x^n}{n!}=$ $\frac{1}{k}\frac{x}{1-x}\sum_nL(n\!-\!1,k\!-\!1)\frac{x^{n-1}}{(n-1)!}=$

$\frac{1}{k(1-x)}\sum_nn\big(L(n,k)-(n\!+\!k\!-\!1)L(n\!-\!1,k)\big)\frac{x^n}{n!}=?$

-

We have \begin{align} f_k(x)&:=\sum_{n\in\Bbb Z}L(n,k)\frac{x^n}{n!}\\ &=\sum_{n\in \Bbb Z}L(n-1,k-1)\frac{x^n}{n!}+\sum_{n\in \Bbb Z}(n+k-1)L(n-1,k)\frac{x^n}{n!}\\ &=\sum_{j\in \Bbb Z}L(j,k-1)\frac{x^{j+1}}{(j+1)!}+\sum_{j\in \Bbb Z}(j+1+k-1)L(j,k)\frac{x^{j+1}}{(j+1)!}\\ &=\sum_{j\in \Bbb Z}L(j,k-1)\frac{x^{j+1}}{(j+1)!}+\sum_{j\in \Bbb Z}L(j,k)\frac{x^{j+1}}{j!}+(k-1)\sum_{j\in \Bbb Z}L(j,k)\frac{x^{j+1}}{(j+1)!}\\ &=\sum_{j\in \Bbb Z}L(j,k-1)\frac{x^{j+1}}{(j+1)!}+xf_k(x)+(k-1)\sum_{j\in \Bbb Z}L(j,k)\frac{x^{j+1}}{(j+1)!} \end{align} hence $$(1-x)f_k(x)=\sum_{j\in \Bbb Z}L(j,k-1)\frac{x^{j+1}}{(j+1)!}+(k-1)\sum_{j\in \Bbb Z}L(j,k)\frac{x^{j+1}}{(j+1)!}.$$ Now we take the derivatives to get $$-f_k(x)+(1-x)f'_k(x)=f_{k-1}(x)+(k-1)f_k(x)$$ hence $$(1-x)f'_k(x)-kf_k(x)=f_{k-1}(x).$$ Multipliying by $(1-x)^{k-1}$ and using the formula for $f_{k-1}$ we get $$(1-x)^kf'_k(x)-k(1-x)^{k-1}f_k(x)=\frac{x^{k-1}}{(k-1)!}$$ so $$((1-x)^kf_k(x))'=\frac{x^{k-1}}{(k-1)!}.$$ Integrating, we get the wanted result up to another term (namely $C(1-x)^k$) but it should vanish using the value at $0$ and the initial definition of Lah numbers.
You are right, thank you! But it seems this exercise would be a lot more difficult if it would just say "compute $\sum_nL(n,k)\frac{x^n}{n!}$", since we couldn't insert $f_{k-1}(x)$. In general, what do we do in such cases? – Leon Jun 17 '12 at 10:12