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

Question

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?

Answer 1

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)$

Answer 2

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