The Lah numbers satisfy the following rising-falling factorials relation
\begin{equation}
x^{\overline{n}} = \sum_{k=0}^{n} L(n, k) x^{\underline{k}},
\end{equation}
where $x^{\overline{n}}$= $x(x+1)\times … \times (x+n-1)$ and $x^{\underline{n}}$ = $x(x-1) \times … \times (x-n+1)$.
What would be the proof of this identity using induction on $n$ with the following recurrence relation
$L(n, k) = L(n-1, k-1) + (n+k-1) L(n-1, k)$?
This is what I tried:
\begin{equation}
x^{\overline{n}} \\ =x^{\overline{n-1}} (x+n+k-1) \\
= \left( \sum_{k=0}^{n} L(n-1, k) x^{\underline{k}} \right) (x+n+k-1) \\
= \sum_{k=0}^{n} L(n-1, k) x^{\underline{k+1}} + (n+k-1) \sum_{k=0}^{n} L(n-1, k) x^{\underline{k}} \\
= \sum_{k=0}^{n} L(n-1, k-1) x^{\underline{k}} + \sum_{k=0}^{n} (n+k-1) L(n-1, k) x^{\underline{k}} \\
= \sum_{k=0}^{n} \left( L(n-1, k-1) x^{\underline{k}} + (n+k-1) L(n-1, k) \right) x^{\underline{k}} \\
= \sum_{k=0}^{n} L(n, k) x^{\underline{k}},
\end{equation}
but I do not think that the proof is correct. Any suggestions? Thanks a lot.
Best Answer
Well, it is wrong because, as I see it, you tried to force the recursion when you do $$x^{\overline{n}} = x^{\overline{n-1}}(x+n+k-1),$$ that is not true, but you can do this:
$$x^{\overline{n}} = x^{\overline{n-1}}(x+n-1)=x^{\overline{n-1}}((x\color{red}{-k})+(n\color{red}{+k}-1)).$$ Now, when you distribute you will get $$\sum _{k = 0}^{n-1}{L(n-1,k)(x-k)x^{\underline{k}}}+\sum _{k = 0}^{n-1}{L(n-1,k)(n+k-1)x^{\underline{k}}}.$$ Notice that $(x-k)x^{\underline{k}}=x^{\underline{k+1}}$ and you would be done.
Ps. Why is the \underline so ugly?