Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
7  
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
1  
Note that this is basically the discrete analogue of solving differential equations. –  Peter Taylor Oct 26 '11 at 9:53
add comment

1 Answer

up vote 2 down vote accepted

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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