Characteristic equation of a recurrence relation

Yesterday there was a question here based on solving a recurrence relation and then when I tried to google for methods of solving recurrence relations, I found this, which gave different ways of solving simple recurrence relations.

My question is how do you justify writing the recurrence relation in its characteristic equation form and then solving for its roots to get the required answer.

For example, Fibonacci relation has a characteristic equation $s^2-s-1=0$.

How can we write it as that polynomial?

Solution 1:

The characteristic equation is the one that a number $\lambda$ should satisfy in order for the geometric series $(\lambda^n)_{n\in\mathbf N}$ to be a solution of the recurrence relation. Another interpretation is that if you interpret the indeterminate $s$ as a left-shift of the sequence (dropping the initial term and renumbering the renaming terms one index lower), then the characteristic equation gives the lowest degree monic polynomial that when applied to this shift operation kills all sequences satisfying the recurrence. In the case of Fibonacci recurrence, applying $s^2-s-1$ to a sequence $A=(a_i)_{i\in\mathbf N}$ gives the sequence $(a_{i+2}-a_{i+1}-a_i)_{i\in\mathbf N}$, which is by definition identically zero if (and only if) $A$ satisfies the recurrence.

A different but related polynomial that is of interest is obtained by reversing the order of the monomials (giving a polynomial starting with constant term $1$), so for Fibonacci it would be $1-X-X^2$. This polynomial $P$ has the property that the formal power series $F=\sum_{i\in\mathbf N}a_iX^i$ associated to a sequence satisfying the recurrence, when multiplied by $P$ gives a polynomial $R$ (with $\deg R<\deg P$), in other words all terms from the index $\deg P$ on are killed. This is basically the same observation as for the shift operation, but the polynomial $R$ permits describing the power series of the sequence, including its initial values, formally as $F=\frac RP$. For the Fibonacci sequence one finds $R=X$ so its formal power series is $F=\frac X{1-X-X^2}$.

Solution 2:

We aren't writing the Fibonacci relation as $s^2-s-1=0$, we are noting a relation between that equation and the Fibonacci relation. We are noting that if $r$ is a solution of the characteristic equation, then $r^n$ is a solution of the recurrence relation.