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

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?

$$h_n=n*h_{n-1}\quad\text{with}\quad h_0=1$$
• I've come up with $h_n = n!(n+1)(n+2)$ as the solution by looking at n=1, 2, 3, 4, 5, 6. Should I now prove that it works for all n using induction? – Irina Sokolova Oct 3 '16 at 2:11
• $n!(n+1)(n+2)=(n+2)!$. Also, proving it by induction would work fine. – AlgorithmsX Oct 3 '16 at 2:15
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)!$$