# 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}$

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$.

-
What do you mean by solve? –  Sigur Feb 3 '13 at 20:46
@Sigur: Find a closed form for $h_n$. –  Brian M. Scott Feb 3 '13 at 20:47
Your initial conditions are either redundant or invalid. Since $h_1 = h_0 + 0 + 0 \implies h_1 = h_0$ and $h_2 = h_1 + 1 + h_0 = 2h_0 + 1$ –  user17762 Feb 3 '13 at 20:50

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.