# 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?

• You'll want to see this... Dec 14, 2011 at 9:20
• You can also look at this from the linear algebra viewpoint, since there is an equivalence between linear difference equations and the repeated multiplication of a Frobenius companion matrix with a vector. The characteristic polynomial of your matrix is the characteristic polynomial of your difference equation. Dec 14, 2011 at 9:24

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}$.
• @Val: As described in the second paragraph above, the polynomial $P$ corresponds to a linear recurrence that is satisfied (from some point onward) by the series$~F$. Given a sequence that ultimately satisfies some linear recurrence, this recurrence is not unique (you can multiply $P$ by any polynomial to get another recurrence) but taking $P$ of minimal degree and with constant coefficient $1$, it does become unique. The corresponding numerator $R$ is then simply the product $R=PF$, and as such it is indeed determined by an initial set of terms of (the sequence encoded by)$~F$. Aug 1, 2013 at 7:01
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.