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$
  • $\begingroup$ nms.lu.lv/wp-content/uploads/2016/04/21-linear-recurrences.pdf $\endgroup$ – enedil Apr 25 '17 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$ – Lord Shark the Unknown Apr 25 '17 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$ – Steven Stadnicki Apr 25 '17 at 15:56
  • $\begingroup$ The characteristic equation is different for irrational roots? $\endgroup$ – Elros Romeo Apr 25 '17 at 15:58
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$
  • $\begingroup$ (+1) Mathematica agrees with this answer. $\endgroup$ – Semiclassical Apr 25 '17 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$
  • $\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$ – Elros Romeo Apr 25 '17 at 15:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.