Showing that the Lah numbers satisfy $L(n + 1, k) = (n + k)L(n, k) + L(n, k - 1)$

Question

Show that the Lah numbers satisfy the following recurrence relation:

$$L(n + 1, k) = (n + k)L(n, k) + L(n, k - 1).$$

Answer 1

Since your definition of the Lah numbers is algebraic rather than combinatorial, you should try for an algebraic proof of the recurrence. Substitute your definition into the desired recurrence to see what it is you have to prove:

$$\frac{(n+1)!}{k!}\binom{(n+1)-1}{k-1}=(n+k)\frac{n!}{k!}\binom{n-1}{k-1}+\frac{n!}{(k-1)!}\binom{n-1}{(k-1)-1}\;,$$

or

$$\frac{(n+1)!}{k!}\binom{n}{k-1}=(n+k)\frac{n!}{k!}\binom{n-1}{k-1}+\frac{n!}{(k-1)!}\binom{n-1}{k-2}\;.$$

In view of the factorials already present, an obvious thing to try is expanding the binomial coefficients into factorials:

$$\frac{(n+1)!}{k!}\cdot\frac{n!}{(k-1)!(n-k+1)!}=(n+k)\frac{n!}{k!}\cdot\frac{(n-1)!}{(k-1)!(n-k)!}+\frac{n!}{(k-1)!}\cdot\frac{(n-1)!}{(k-2)!(n-k+1)!}\;,$$

or

$$\frac{(n+1)!n!}{k!(k-1)!(n-k+1)!}=\frac{(n+k)n!(n-1)!}{k!(k-1)!(n-k)!}+\frac{n!(n-1)!}{(k-1)!(k-2)!(n-k+1)!}\;.$$

To prove this, just combine the fractions on the righthand side over the common denominator $k!(k-1)!(n-k+1)!$ and do a little straightforward algebra.