Sum of product of Stirling numbers

Question

We have for $n>0$, $k>0$ $$\sum\limits_{j=1}^{\min(n,k)}(j!)^2{n\brace j}{k+1\brace j+1}=\sum\limits_{j=0}^{\min(n,k-1)}j!(j+1)!{n+1\brace j+1}{k\brace j+1}$$ How can we prove it?

Answer 1

Using the recurrence relation for the Stirling numbers of the second kind \begin{eqnarray*} {k+1\brace j+1}=(j+1){k\brace j+1}+{k\brace j}. \end{eqnarray*} The sum becomes \begin{eqnarray*} S&=&\sum\limits_{j=1}^{\min(n,k)}(j!)^2{n\brace j}{k+1\brace j+1} \\ &=& \sum\limits_{j=1}^{\min(n,k)}(j!)((j+1)!){n\brace j}{k\brace j+1} +\sum\limits_{j=1}^{\min(n,k)}(j!)^2{n\brace j}{k\brace j} \end{eqnarray*} shift the second summation variable by $1$ \begin{eqnarray*} S&=& \sum\limits_{j=0}^{\min(n,k-1)}(j!)((j+1)!){k\brace j+1} \left({n\brace j}+(j+1){n\brace j+1}\right)\\ \end{eqnarray*} Now use the recurrence formula again \begin{eqnarray*} {n+1\brace j+1}={n\brace j}+(j+1){n\brace j+1} \end{eqnarray*} & we are done.