Linear Recurrences

A linear recurrence is a relation between the terms of a sequence which is represented as $x_n = Ax_{n-1}+Bx_{n-2}+\cdots$

One common recurrence is the Fibonacci sequence defined by $F_1 = F_2 = 1$ and $F_n = F_{n-1}+F_{n-2}$.

For a second order linear recurrence, one of the form $x_n = Ax_{n-1}+Bx_{n-2}$, we can find a general formula for the $n$th term($x_n$). Assume that we know two of the terms are already.

We have that $x_n=c_1 r_1^n + c_2 r_2^n$ where $r_1$ and $r_2$ are the roots of the quadratic $x^2-Ax-B = 0.$

Now, what's up with these constants $c_1$ and $c_2$??

WELL....WE SOLVE FOR THESE CONSTANTS!

If we already know two of the terms let's say $x_a$ and $x_b$, we simply have to solve these systems of linear equations for $c_1$ and $c_2$:

$x_a = c_1 r_1^{a}+c_1r_2^{a}$

$x_b = c_1 r_1^{b}+c_1r_2^{b}$

---

$\textbf{Characteristic equation}$ (defined for linear Homogeneous recurrences only)

A characteristic equation is an equation related to the recurrence relation which is important for generalizing a recurrence relation's $n^{th}$ term.

Characteristic equation is obtained from the following steps,

$\mathbf{1.}$ Write the term of the homogeneous recurrence relation, which has the least sub-script number, as $x^0$

$\mathbf{2.}$ Write each of the terms in the form of $x^k$ depending on their subscript

($n$ is the subscript in $a_n$)

$\mathbf{3.}$ Get all the terms, written in the form $x^k$, along with their coefficients, in the form of an equation in $x$, which will be the characteristic equation.

---

Worked example-

$a_n=3a_{n-1}+a_{n-2}-6a_{n-3}$

Lowest subscript is $a_{n-3}$, so write it as $x^0$.

Further, we'll write $a_{n-2}=x^1,a_{n-1}=x^2,a_n=x^3$

from this,

$\quad x^3=3x^2+x-6\\ \therefore x^3-3x^2-x+6=0$

We conclude that Characteristic equation of $a_n=3a_{n-1}+a_{n-2}-6a_{n-3}$ is $$x^3-3x^2-x+6=0$$

---

---