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?
Best Answer
One may use generating functions to solve for the solution; see Chapter 1 of a book I highly recommend, generatingfunctionology, or for a very small example, a recent answer of mine. It involves using the recurrence to derive a rational function for as the generating function, then using partial fraction decomposition to write it as a sum of geometric series (or powers thereof).
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.