Solve the recurrence relation: $h_n=(n+1)h_{n-1}, n \ge 1$, initial value $h_0=2$.

Question

Solve recurrence relation:

$h_n=(n+1)h_{n-1}, n \ge 1$, initial value $h_0=2$

Good evening, all. I find myself stuck on how to solve linear homogeneous recurrence relations with variable coefficients without essentially guessing at the answer. Could anyone please provide some pointers?

Answer 1

Hint: Here is a simpler, but similar recurrence relation:

$$h_n=n*h_{n-1}\quad\text{with}\quad h_0=1$$

You may recognize that as the definition of the factorial.

Answer 2

Considering $$h_n=(n+1)\,h_{n-1}$$ we can suppose that factorial would appear in the result. So, assume $$h_n=a (n+k)!$$ then $$\Delta=h_n-(n+1)h_{n-1}=a(n+k)!-a(n+1)(n+k-1)!=0$$ $$\Delta=a(n+k)(n+k-1)!-a(n+1)(n+k-1)!=0$$ $$\Delta=a(n+k-1)!(n+k-n-1)=a(n+k-1)!(k-1)=0\implies k=1$$ So $$h_n=a(n+1)!$$