Full Solution to Linear Recurrences

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

---

---

Let us think about a normal linear recurrence. It is generally of the form

$$x_n = Ax_{n-1} + Bx_{n-2}$$

We can convert this into its characteristic equation which is

$$x^2 - Ax - B = 0$$

Solving this characteristic equation we can find the roots $r_1$ and $r_2$. We can now solve with these roots as long as $r_1 \neq r_2$.

$$x_n = P r_1^n + Q r_2^n$$

If we have $r_1 = r_2$, then we have

$$x_n = P r^n + Qnr^n$$

Using this we can find closed forms for linear recurrences.