# Solve recurrence relation: $a_n=3a_{n−1}+5a_{n−2}−7a_{n−3}$

I hope can you help me, I want to solve this recurrence relation: $a_n=3a_{n−1}+5a_{n−2}−7a_{n−3}$ with initial values $a_1=4, a_2=8, a_3=2$

Using synthetic division I get the roots: $1, 1-2\sqrt{2}$ and $1-2\sqrt{2}$

What are the characteristic equation for three different roots? I guess that:

$a_n = c_1(r_1)^n + c_2(r_2)^n + c_3(r_3)^n$ where $r_1, r_2, r_3$ are the roots.

Can you help me solve this problem?

• nms.lu.lv/wp-content/uploads/2016/04/21-linear-recurrences.pdf – enedil Apr 25 '17 at 15:53
• You are on the right lines: you need to put in $n=1$, $2$ and $3$ to get linear equations for the $c_i$. – Lord Shark the Unknown Apr 25 '17 at 15:53
• Note that you have a typo: the two irrational roots have to be 'conjugate' to each other (they should be $1\pm2\sqrt2$, presumably.) – Steven Stadnicki Apr 25 '17 at 15:56
• The characteristic equation is different for irrational roots? – Elros Romeo Apr 25 '17 at 15:58

## 2 Answers

Recurrence $a_n=3a_{n−1}+5a_{n−2}−7a_{n−3}$ has characteristic polynomial $x^3 - 3x^2 - 5x + 7 = 0$ which has roots $x=1$, $x=1 - 2\sqrt{2}$, and $x=1 +2\sqrt{2}$.

That means your recurrence has form $a_n = \alpha \cdot 1^n + \beta \cdot (1-2\sqrt{2})^n + \gamma \cdot (1+2\sqrt{2})^n$.

Substitute in the values you know:

$4 = \alpha \cdot 1^1 + \beta \cdot (1-2\sqrt{2})^1 + \gamma \cdot (1+2\sqrt{2})^1$

$8 = \alpha \cdot 1^2 + \beta \cdot (1-2\sqrt{2})^2 + \gamma \cdot (1+2\sqrt{2})^2$

$2 = \alpha \cdot 1^3 + \beta \cdot (1-2\sqrt{2})^3 + \gamma \cdot (1+2\sqrt{2})^3$

This leads to solution $\alpha = \frac{21}{4}$, $\beta = \frac{3}{8} + \frac{1}{2\sqrt{2}}$, and $\gamma = \frac{3}{8} - \frac{1}{2\sqrt{2}}$.

$a_n = \frac{21}{4}+ (\frac{3}{8} + \frac{1}{2\sqrt{2}})\cdot (1-2\sqrt{2})^n + (\frac{3}{8} - \frac{1}{2\sqrt{2}})\cdot (1+2\sqrt{2})^n$

This can be flattened down a little:

$a_n = \frac{1}{8} ((3 - 2\sqrt{2}) (1 + 2 \sqrt{2})^n + (3 + 2 \sqrt{2}) (1 - 2 \sqrt{2})^n + 42)$

• (+1) Mathematica agrees with this answer. – Semiclassical Apr 25 '17 at 16:15

an small tip :D if you make the ansatz $a_n =r^{n}$

the recurrence equation becomes

$r^{n}=3r^{n-1}+5r^{n-2}-7r^{n-3}$

multiply all by $r^{3}$ you get

$r^{n+3}=3r^{n+2}+5r^{n+1}-7r^{n}$

divide all by $r^{n}$ you get the polynomial

$r^3 =3r^2+5r-7$

get the roots of this polynomial and you get the solution

• Thanks for your answer, I did that to get my roots. The problem is that I am lost with the equations to get the constants @.@ – Elros Romeo Apr 25 '17 at 15:59