# Recurrence Relation, closed-form (linear, 2nd order, constant coeff, homogeneous)

If I have a recurrence relation, such as $h_n = h_{n-1} + 2h_{n-2}$, is there a rigid method to find a closed formula for $h_n$?

As of right now, I just solve for the first few terms $h_0, h_1, h_2, h_3$, etc. until I notice a pattern and try to brute force an answer, but some patterns are not easily discerned by such a method (such as this one).

For reference this particular sequence is: $1, 3, 5, 11, 21, 43, \dots$

I was given that $h_0 = 1$, and $h_1 = 3$.

I figured out that the answer is $h_n = \dfrac{2^{n+2}-(-1)^{n+2}}{3}$ after a lot of trial and error. Is there a better way to find this?

-
The characteristic equation $x^2=x+2$ has distinct roots $x=2$ and $x=-1$, so the solution will be of the form $h_n=a2^n+b(-1)^n$. You can solve for $a$ and $b$ with the initial conditions and basic linear algebra. See en.wikipedia.org/wiki/… and similar resources. –  anon Oct 26 '11 at 4:28
you may write $(-1)^n$ instead of $(-1)^{n+2}$ –  pedja Oct 26 '11 at 6:45
Note that this is basically the discrete analogue of solving differential equations. –  Peter Taylor Oct 26 '11 at 9:53

One speedy method that falls out of this methodology is that of characteristic polynomials: take $$c_ka_{n+k}+\cdots+c_0a_n=0$$ as a linear recurrence equation in $a_n$ (you may have to reindex and move things around a bit first to get it in this form) and use it to write out the characteristic polynomial: $$p(x)=c_kx^k+\cdots+c_1x+c_0.$$ If the roots $r_i$ of this polynomial are distinct, we can write the general form of $a_n$ as a linear combination of exponentials with these roots as bases: $$a_n=b_1r_1^n+\cdots+b_kr_k^n.$$ Plugging this expression into the LHS of the recurrence equation gives $\sum_ib_ip(r_i)$, or $0$, so it is indeed a solution. We may solve for the coefficients by writing $\sum_ib_ir_i^\ell=a_\ell$ for the indices of the initial conditions $a_\ell$ and solving for the $b_i$'s using methods of linear algebra (because this is a linear system, in fact). Linear algebraic methods can also prove that this formula spans all possible solutions.
The case when the roots $r_i$ are not distinct is more complicated; factors of the form $q_i(n)r_i^n$ must be invoked with $q_i$ a polynomial of degree one less than the multiplicity of the root $r_i$ of $p$. How-ever, similar reasoning and methods still apply.