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?
 A: 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)$
A: 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
