Find a closed form for the recurrence relation $h_{n}=h_{n-1}+(n-1)+\sum_{k=1}^{n-1} {n-2 \choose k-1}h_{k-1}$

Question

I have a recurrence equation as follows: $$h_{n}=h_{n-1}+(n-1)+\sum_{k=1}^{n-1} {n-2 \choose k-1}h_{k-1}\;,$$ with $h_{0}=0,h_{1}=1,h_{2}=2$.

Answer 1

Rewrite the recurrence as: $$ h_{n + 2} = h_{n + 1} + n + 1 + \sum_{0 \le k \le n} \binom{n}{n - k} h_k $$ Define the exponential generating function (because of the binomial convolution): $$ H(z) = \sum_{n \ge 0} h_n \frac{z^n}{n!} $$ Using the properties of exponential generating functions: $$ H''(z) - H'(z) - e^z H(z) = (1 + z) e^z $$ Maxima doesn't know how to solve this, so I have little hope for a closed form solution.