# Finding a solution to a recurrence relation

Find the solution to $$a_n = 5a_{n−2} − 4a_{n−4}$$ with $$a_0 = 3$$ $$a_1 = 2$$ $$a_2 = 6$$ $$a_3 = 8$$

My answer: Observe that the degree of recurrence is 4. Hence, the characteristic equation is: $x^4 - 5x^2 +4 = 0$. Solving for $y=x^2$ we get $y_1=1$, $y_2 = 4$. Hence, the solutions are $x_1 = -1$, $x_2 = 1$, $x_3 = -2$, $x_4 = 2$. This implies that $a_n = \alpha_1(-1)^n + \alpha_2 + \alpha_3 (-2)^n + \alpha_4(2^n)$. It remains to solve the initial conditions for $\alpha_i-s : \alpha_1 = 1, \alpha_2 = 1, \alpha_3 = 0, \alpha_4 = 1$.

Where should I go from here to ensure the answer is fully answered and complete? Thank you!

-
I think you're going to need to correct some subscripts in your relation in order to clarify this problem. (Thank you.) –  RecklessReckoner Apr 15 '13 at 0:17
What subscripts? –  tekman22 Apr 15 '13 at 0:18

Since the recurrence relation is linear, the general solution is a linear combination of 4 particular solution you found. Initial conditions determine unknown constants: $$a_n = \alpha_1 + \alpha_2 (-1)^n + \alpha_3 2^n + \alpha_4 (-2)^n$$ Now substitute initial conditions for $n=0$, $n=1$, $n=2$ and $n=3$ to find $\alpha_1$, $\alpha_2$, $\alpha_3$ and $\alpha_4$.

-
Hmm where did you get that equations for $a_n$ ? –  tekman22 Apr 15 '13 at 0:21
I edited and fixed the original question and answer. Could you just make sure it's fixed in your answer as well? Thanks! –  tekman22 Apr 15 '13 at 0:24

Just for kicks, use generating functions on this one. Define $A(z) = \sum_{n \ge 0} a_n z^n$. Your recurrence is: $$a_{n + 4} = 5 a_{n + 2} - 4 a_n \quad a_0 = 3, a_1 = 2, a_2 = 6, a_3 = 8$$ Using properties of ordinary generating afunctions: $$\frac{A(z) - a_0 - a_1 z - a_2 z^2 - a_3 z^3}{z^4} = 5 \frac{A(z) - a_0 - a_1 z}{z^2} - 4 A(z)$$ Solving for $A(z)$, written as partial fractions: $$A(z) = \frac{1}{1 - z} + \frac{1}{1 + z} + \frac{1}{1 - 2 z}$$ Expanding the geometric series: $$a_n = 1 + (-1)^n + 2^n$$

-
So my answer is correct? –  tekman22 Apr 15 '13 at 0:35
Still not sure lol –  tekman22 Apr 15 '13 at 1:25
@jtm22, check yourself if all the developments agree and if the results are the same... –  vonbrand Apr 15 '13 at 2:40