Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
What do you mean by solve? –  Sigur Feb 3 '13 at 20:46
2  
@Sigur: Find a closed form for $h_n$. –  Brian M. Scott Feb 3 '13 at 20:47
2  
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

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.