1
$\begingroup$

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?

$\endgroup$
0
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Irina Sokolova Oct 3 '16 at 2:11
  • $\begingroup$ $n!(n+1)(n+2)=(n+2)!$. Also, proving it by induction would work fine. $\endgroup$ – AlgorithmsX Oct 3 '16 at 2:15
0
$\begingroup$

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)!$$

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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