1
$\begingroup$

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?

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

2 Answers 2

3
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ (+1) Mathematica agrees with this answer. $\endgroup$ Commented Apr 25, 2017 at 16:15
1
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ 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 @.@ $\endgroup$ Commented Apr 25, 2017 at 15:59

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .